算法1
(普遍dp)
#include <iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j];//不选择放该物品的情况
if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);//当能放下第i个物品时,进行抉择放入的话合不合适
}
}
cout<<dp[n][m];
return 0;
}
算法2
(优化后)
#include <iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[m];
return 0;
}
对于01背包一维优化的一点理解：
二维转化为一维：
删掉了第一维：在前i个物品中取。
f[j]表示：拿了总体积不超过j的物品，最大总价值。
为何能转化为一维？
二维时的更新方式：f[i][j]=max(f[i - 1][j] ,f[i - 1][j - v[i]] + w[i]);
1.我们发现，对于每次循环的下一组i，只会用到i-1来更新当前值，不会用到i-2及之前值。于是可以在这次更新的时候，将原来的更新掉，反正以后也用不到。
所以对于i的更新，只需用一个数组，直接覆盖就行了。
2.我们发现，对于每次j的更新，只需用到之前i-1时的j或者j-v[i]，不会用到后面的值。
所以为了防止串着改，我们采取从后往前更新的方式，用原来i-1的数组来更新i。
（如果从前往后更新的话，前面的更新过之后，会接着更新后面的值，这样就不能保证是用原来i-1的数组来更新i的了）
如何转化为一维呢？
只用一个数组，每次都覆盖前面的数组。
1.如果当前位置的东西不拿的话，和前一位置的信息（原来i-1数组的这个位置上的值）是相同的，所以不用改变。
2.如果当前位置的东西拿了的话，需要和前一位置的信息（原来i-1数组的这个位置上值）取max。
所以，更新方式就为：f[j]=max(f[j],f[j-v[i]]+w[i]);
整个更新方式就相当于：
