http://202.120.80.191/problem.php?problemid=2585
f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][j],f[i-1][j-w[i]]+d[i]}
可以看出，第i个状态只和前一个状态有关。因此，只需要一个一维数组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]);
注意，第二层循环要从后往前。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]].
该优化，把空间复杂度从O(mn)降到了O(m).
还有一个优化：
由于最后的结果是存放在a[m]中，而求a[m]只需要知道a[j-w[n]]即可，依次类推，当之考虑前i个物品时，只需要知道a[j-sum(n..i)]即可。 所以优化后的伪代码为：
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;
}