动态规划-背包问题总结
01背包问题：
01背包其实是一个递推问题，每次都是最优解不断推出最终结果。一维和二维都要掌握。
动态方程：
F[ i , v ] = max { F[ i−1 , v ] , F[ i−1 , v−Ci ] + Wi } ，意思是：当选第 i 个物品时 F [ i-1 , v ] 代表不放第 i 件物品，F [ i-1 , v - Ci ] + Wi ; 代表放第 i 件物品，第 i-1 件物品得到的最优解加上第 i 件物品的价值。可以用一维数组 F[ i ] = max (F[ i ] ,F[ i - ci ]+wi ) ;
代码（二维数组）：
-
memset(dp,0,sizeof(dp)) ;
-
for(int i=1 ;i<=n ;i++) // 最终答案为f[n][c]
-
{
-
scanf("%d%d",&v,&w) ; // 边输入边计算
-
for(int j=0 ;j<=c ;j++) // 这一行中 j 不能初始化为 v 因为如果这样 i 时就记录（得）不到
-
{ // i-1 时已经得到的最优解
-
dp[i][j]=(i==1 ? 0 : dp[i-1][j]) ;
-
if(j>=v&&dp[i][j]<dp[i-1][j-v]+w)
-
dp[i][j]=dp[i-1][j-v]+w ;
-
}
-
}
代码（一维滚动数组）：
-
memset(dp,0,sizeof(dp)) ;
-
for(int i=1 ;i<=n ;i++)
-
{
-
scanf("%d%d",&v,&w) ;
-
for(int j=C ;j>=v ;j--) // 这一行可以让 j 大于等于 v 因为结束后f[]数组
-
if(dp[j]<dp[j-v]+w) // 已经把i-1时的最优解保存在里面（因为是一维）
-
dp[j]=dp[j-v]+w ;
-
}
题目类型：
1. 裸题. 2. 有的只给一个价值，只要把价值同时看成体积就可以了. 3. 有的是求一些物品平分问题（可以用搜索）.4. 让求恰好装满（理解：初始化的 F 数组事实上就是在没有任何物品可以放 入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什 么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于 未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包 都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了）.5.让打印路径。
完全背包：
完全背包只学习了一种方法，二进制方法和多重背包一样。
动态方程：
(1) 转化为01背包 f [ i ][ v ] = max { f[ i - 1 ][ v - k*c[ i ] ] + k*w[i] ] { 0<=k*c[i]<=v }
(2) F[ i ] = max ( F[ i ],F[ i - ci ] + wi ) ; 和 01 背包中的一维数组的一样只是枚举的顺序不同，这里讲一下枚举的循序（背包九讲）：首先想想为什么 01 背包中要按照 v 递减的次序来循环。 让 v 递减是为了保证第 i 次循环中的状态 F[i,v] 是由状态 F[i−1,v −Ci] 递推而来。 换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这件策 略时，依据的是一个绝无已经选入第 i 件物品的子结果 F[i−1,v −Ci]。而现在完全背 包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时， 却正需要一个可能已选入第 i 种物品的子结果 F[i,v−Ci]，所以就可以并且必须采用 v 递增的顺序循环。这就是这个简单的程序为何成立的道理。
多重背包：
多重背包只学了二进制优化二维）：
-
在这之前，我空间好像转过一个背包九讲，现在我就只对
-
01背包和多重背包有点印象了
-
-
先说下 01 背包，有n 种不同的物品，每个物品有两个属性
-
size 体积，value 价值，现在给一个容量为 w 的背包，问
-
最多可带走多少价值的物品。
-
-
int f[w+1]; //f[x] 表示背包容量为x 时的最大价值
-
for (int i=0; i<n; i++)
-
for (int j=w; j>=size[i]; j++)
-
f[j] = max(f[j], f[j-size[i]]+value[i]);
-
-
如果物品不计件数，就是每个物品不只一件的话，稍微改下即可
-
for (int i=0; i<n; i++)
-
for (int j=size[i]; j<=w; j++)
-
f[j] = max(f[j], f[j-size[i]]+value[i]);
-
-
f[w] 即为所求
-
-
初始化分两种情况
-
1、如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;
-
2、如果不需要正好装满 f[0~v] = 0;
-
-
多重背包问题要求很简单，就是每件物品给出确定的件数，求
-
可得到的最大价值
-
-
多重背包转换成 01 背包问题就是多了个初始化，把它的件数C 用
-
分解成若干个件数的集合，这里面数字可以组合成任意小于等于C
-
的件数，而且不会重复，之所以叫二进制分解，是因为这样分解可
-
以用数字的二进制形式来解释
-
比如：7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以
-
组合成任意小于等于7 的数，而且每种组合都会得到不同的数
-
15 = 1111 可分解成 0001 0010 0100 1000 四个数字
-
如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成
-
7以内任意一个数，加上 0110 = 6 可以组合成任意一个大于6 小于13
-
的数，虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种
-
思想去把多件物品转换为，多种一件物品，就可用01 背包求解了。
-
-
-
看代码：
-
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;
-
}
-
}
-
现在用count 代替 n 就和01 背包问题完全一样了
分组背包(背包九讲)：
有n件物品和一个容量为V的背包，第 i 件物品的费用是 Ci ,价值是 Wi , 这些物品被划分为 k 组，每组中的物品相互冲突，最多选一件，求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法：
这个问题变成了每组物品有若干中策略：是选择本组的某一件，还是一件都不选。也就是说设F[ k,v ] 表示前 k 组物品花费费用 v 能取得的最大权值，则有：
F[ k , v ] = max { F[ k-1 , v ] ,F[k-1,v-Ci ] +Wi } ;
同样可以优化为一维。假设有 k 组物品每组有 m 个物品：
-
for(int i=0 ;i<k ;i++) // 组数
-
for(int j=V ;j>=0 ;j--) // V 为总体积
-
for(int k=0 ;k<m&&v[i][k]<=j ;k++) // 依次放入同组的每个物品
-
dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]) ;
开始一直不明白这样为什么能做到每组物品只选择一件，自己模拟了一下才恍然大悟，因为放同一组的时候体积是逆序放的，而且放同一体积时同一组的都放一次，这样就保证了每组物品最多选一件（可以不选择）。
变形：每组至少选择一件（例题：HDU 3033 ）。
如果这样初始化时就要注意了，只有第 0 组所有的情况是正确的（组数从 1 开始），so ~ > 其它赋值为负无穷。因为每组物品可以选择多件，因此要把第二层 for 循环与第三层for 循环互换一下。这样就可以保证每组物品可以选择多件。
推荐博客：01背包总结 建议先看背包九讲
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/18078085
- 点赞
- 收藏
- 关注作者
评论（0）