http://202.120.80.191/problem.php?problemid=2585
f[i][j]表示前i件物品恰放入一個容量為j的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：
f[i][v]=max{f[i-1][j],f[i-1][j-w[i]]+d[i]}
可以看出，第i個狀態(tài)只和前一個狀態(tài)有關。因此，只需要一個一維數(shù)組a[maxn],偽代碼為
for(int i=1;i<=n;i++)
for(int j=m;j>=w[i];j--)
a[j]=max(a[j],a[j-w[i]]+d[i]);
注意，第二層循環(huán)要從后往前。max(a[j],a[j-w[i]])中，a[j]表示的是只考慮前i-1個物品，且背包容量是j時可以獲得的最大值，即遞推公式中的f[i-1][j]，a[j-w[i]]則是f[i-1][j-w[i]].
該優(yōu)化，把空間復雜度從O(mn)降到了O(m).
還有一個優(yōu)化：
由于最后的結果是存放在a[m]中，而求a[m]只需要知道a[j-w[n]]即可，依次類推，當之考慮前i個物品時，只需要知道a[j-sum(n..i)]即可。 所以優(yōu)化后的偽代碼為：
for(int i=1;i<=n;i++)
{
bound=max(w[i],m-sum[n..1]);
for(int j=m;j>=bound;j--)
a[j]=max(a[j],a[j-w[i]]+d[i]);
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int maxn=3403;
int w[maxn],d[maxn],sum[maxn];
int a[12881];
int n,m;
void solve()
{
int bound;
sum[n]=w[n];
for(int i=n-1;i>0;i--)
sum[i]=sum[i+1]+w[i];
for(int i=0;i<=m;i++)
a[i]=0;
for(int i=1;i<=n;i++)
{
//bound=max(w[i],m-sum[i]);
bound=w[i]>m-sum[i]?w[i]:m-sum[i];
for(int j=m;j>=bound;j--)
a[j]=a[j]>a[j-w[i]]+d[i]?a[j]:a[j-w[i]]+d[i];
}
printf("%d\n",a[m]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&d[i]);
solve();
return 0;
}