根据这几天的学习情况，总结一下对于背包的理解和一些实现方式：
1.大名鼎鼎的0/1背包：这个就不多总结了
2.完全背包：
应该明白，通俗意义上完全背包指的是对于n个价值为v,重量为w的物品，每个物品可以无限次的取（而对于0/1来讲，则是只能取一次）
这怎么处理？
如果按照解01背包时的思路，令 f[i][j]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
f[i][j]=max(f[i][j],f[i-1][j-k*w[i]+k*v[i]);
但很不幸的是，这种情况大多是超时的
我们用滚动数组优化，具体优化方式如下：
既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第 i i i种物品最多选 V/c[i]件，于是可以把第 i种物品转化为 V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
1 for (int i = 1; i <= n; i++)//大循环 2 for (int j = c[i]; j <= V; j++)//正序啦，注意是正序 3 dp[j] = max([dpj], dp[j - c[i]] + w[i]);//状态以及转移方程
03-05 07:09