算法——背包问题 01背包+完全背包+多重背包
01背包：https://biancheng.love/problem/51/index
有n 种不同的物品，每个物品有两个属性，weight重量，value 价值，现在给一个容量为 w 的背包，问最多可带走多少价值的物品。
int f[w+1]; //f[x] 表示背包容量为x 时的最大价值for(int i = 1; i <= n;i++){for(long long j = weight[i]; j <= m; j++){f[j] = max(f[j], f[j - weight[i]] + value[i]);/*long long tmp = f[j - weight[i]] + value[i];if(f[j] < tmp)f[j] = tmp;*/}}
[cpp] view plain co
V=10，N=3，c[]={3,4,5}, w={4,5,6}
（1）背包不一定装满
计算顺序是：从右往左，自上而下：因为每个物品只能放一次，前面的体积小的会影响体积大的
（2）背包刚好装满
计算顺序是：从右往左，自上而下。注意初始值，其中-inf表示负无穷
完全背包：https://biancheng.love/problem/100/index
如果物品不计件数，就是每个物品不只一件的话，稍微改下即可
for (int i = 1; i <= n; i++){for (int j = m; j >= weight[i]; j--)f[j] = max(f[j], f[j - weight[i]] + value[i]);}
[cpp] view pla
f[w] 即为所求
初始化分两种情况：
1、如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;
2、如果不需要正好装满 f[0~v] = 0;
V=10，N=3，c[]={3,4,5}, w={4,5,6}
（1）背包不一定装满
计算顺序是：从左往右，自上而下： 每个物品可以放多次，前面的会影响后面的
（2）背包刚好装满
计算顺序是：从左往右，自上而下。注意初始值，其中-inf表示负无穷
多重背包：https://biancheng.love/problem/122/index
多重背包问题要求很简单，就是每件物品给出确定的件数，求可得到的最大价值
多重背包转换成 01 背包问题就是多了个初始化，把它的件数C 用二进制分解成若干个件数的集合，这里面数字可以组合成任意小于等于C的件数，而且不会重复，之所以叫二进制分解，是因为这样分解可以用数字的二进制形式来解释
比如：7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以组合成任意小于等于7 的数，而且每种组合都会得到不同的数
15 = 1111 可分解成 0001 0010 0100 1000 四个数字
如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成 7以内任意一个数，即1、2、4可以组合为1——7内所有的数，加上 0110 = 6 可以组合成任意一个大于6 小于等于13的数，比如12，可以让前面贡献6且后面也贡献6就行了。虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种思想去把多件物品转换为，多种一件物品，就可用01 背包求解了。
看代码：
[cpp] view plain copy
- int n; //输入有多少种物品
- int c; //每种物品有多少件
- int v; //每种物品的价值
- int s; //每种物品的尺寸
- int count = 0; //分解后可得到多少种物品
- int value[MAX]; //用来保存分解后的物品价值
- int size[MAX]; //用来保存分解后物品体积
- scanf(“%d”, &n); //先输入有多少种物品，接下来对每种物品进行分解
- while (n—) //接下来输入n中这个物品
- {
- scanf(“%d%d%d”, &c, &s, &v); //输入每种物品的数目和价值
- for (int k=1; k<=c; k<<=1) //<<右移 相当于乘二
- {
- value[count] = k*v;
- size[count++] = k*s;
- c -= k;
- }
- if (c > 0)
- {
- value[count] = c*v;
- size[count++] = c*s;
- }
- }
定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是满足n-2^k+1>0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。
证明如下：
（1） 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]；
（2）如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.
（3）如果t>=2^k,设s=n-2^k+1，则t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。
（证毕！）
现在用count 代替 n 就和01 背包问题完全一样了
可参考杭电2191（多重背包用01和完全背包）
参考资料：http://blog.csdn.net/lyhvoyage/article/details/8545852
墨蓝
港控/mmm°
ゞ 浴缸里的玫瑰
太过爱你忘了你带给我的痛
还没有评论，来说两句吧...