1.0-1背包
状态转移方程：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]) ------>压缩为一维 dp[j] = max(dp[j], dp[j - w[i]] + c[i]) 逆向
自写垃圾版：
问题：20行代码中变量j为什么即可初始为0也可为1？ ----------------初始容量为0不影响结果，应该初始为1.
20行for循环可反向？
进化版
化一维数组 ----每层刷新，从后往前
2.完全背包
dp公式：dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+c[i]) ------->压缩 为一维数组 dp[j] = max(dp[j],dp[j-w[i]]+c[i]) 顺向
如：6重量拿一个3后还剩3重量，3重量最优解在i行已经出现过了
进化版
const int MAXN = 1005;
int v[MAXN]; // 体积
int w[MAXN]; // 价值
int f[MAXN]; // f[i][j], j体积下前i个物品的最大价值
int main()
{
int n, m; //n物体个数 ，m背包总体积
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 = v[i]; j <= m; j++)
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
cout << f[m] << endl;
return 0;
}
3.扩展
01背包问题回溯：在使得背包内总价值最大的情况下，背包内装了那些物品？
