背包问题

01背包、完全背包、多重背包的总结

动态规划—简单背包问题

零 开始之前

什么是动态规划？

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法叫做动态规划。

什么时候能用动态规划？

动态规划常常适用于有重叠子问题和最优子结构性质的问题。

什么是最优子结构？

当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

什么是重叠子问题？

在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

动态规划该怎么做？

1、确定状态

2、确定状态转移方程

3、从大到小（记忆化+递归）、从小到大（递推）

一个简单的例子

爬楼梯问题

你正在爬一个有n个台阶的楼梯，每次只能上1个或者2个台阶，那么到达顶端共有多少种不同的方法？

• 确定状态 dp[i] 表示有 i 个台阶时的方法数
• 确定转移方程 dp[i] = dp[i - 1] + dp[i - 2]。
• 递归加记忆化求解：

#include <bits/stdc++.h> #define ll long long #define N 5123 using namespace std; int dp[N]; int F(int n){ if(n == 1 || n == 2)return n; //边界 if(dp[n] != 0)return dp[n]; //记忆化 return F(n - 1) + F(n - 2); // 转移 } int main(){ int n; scanf(“%d”, &n); printf(“%d\n”, F(n)); }

• 递推求解：

#include <bits/stdc++.h> #define ll long long #define N 5123 using namespace std; int dp[N]; int main(){ int n; scanf(“%d”, &n); dp[1] = 1; dp[2] = 2; //边界 for(int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; //转移 printf(“%d\n”, dp[n]); }

什么是背包问题？

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。背包问题是动态规划问题的一种类型。

一 0-1背包问题

简化的 01-背包 ——装箱问题

题目链接：（https://www.acwing.com/problem/content/1026/）

题目大意：有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

确定状态

dp[i][j] 表示前 i 个物品能否组成体积 j

确定转移方程

dp[i][j] = 1 (f[i - 1][j] == 1 || f[i - 1][j - v[i]] == 1)

dp[i][j] = 0 (else)

列表验证

样例输入: 24 6

​ 8 3 12 7 9 7

样例输出：0

递推解决

#include <bits/stdc++.h> #define ll long long #define N 21234 using namespace std; int dp[31][N], a[31]; int main() { int v, n; scanf(“%d %d”, &v, &n); for(int i = 1; i <= n; i++)scanf(“%d”, &a[i]); dp[0][0] = 1; int ans = v; for(int i = 1; i <= n; i++){ for(int j = 0; j <= v; j++){ if(dp[i - 1][j] == 1)dp[i][j] = 1; if(j - a[i] >= 0 && dp[i - 1][j - a[i]] == 1)dp[i][j] = 1; if(dp[i][j] == 1)ans = min(ans, v - j); } } printf(“%d\n”, ans); }

01滚动

我们可以看到每一行的结果实际上只与上一行有关，所以就可以01滚动——f[i][0,1] 一行记录前一行的值，另一行记录当前行的值……

就地滚动

对于本题更加常用的方法是就地滚动，顾名思义只用一个一维数组了!之前的状态和当前的状态都记在同一个数组里了！

比如：

for(int i = 1; i <= n; i++){ for(int j = 0; j <= v; j++){ if([j] == 1)dp[j] = 1; if(j - a[i] >= 0 && dp[j - a[i]] == 1)dp[j] = 1; } }

但是简单的变成一维以后有可能发出问题

比如：

假设第一个物品体积3

一个物品被使用了多次！

如何解决？

我们只需改变内层循环的顺序即可！

for(int i = 1; i <= n; i++){ for(int j = v; j >= 0; j–){ if([j] == 1)dp[j] = 1; if(j - a[i] >= 0 && dp[j - a[i]] == 1)dp[j] = 1; } }

问题得到解决！

0-1背包问题

题目链接：（https://www.acwing.com/problem/content/2/）

题目大意：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

确定状态

f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值

确定状态转移方程

两种情况：

1.不放当前物品 f[i][j] = f[i-1][j]

2.放当前物品 f[i][j] = f[i-1][j-c[i]]+w[i]

f[i][j]=max{f[i-1][j],f[i-1][j-c[i]]+w[i]}

列表验证

就地滚动

#include <bits/stdc++.h> using namespace std; #define N 2123 #define ll long long int dp[N], u[N], v[N]; int main() { ios::sync_with_stdio(0); int n, w, ans = 0; cin >> n >> w; for(int i = 1; i <= n; i++){ cin >> u[i] >> v[i]; } for(int i = 1; i <= n; i++){ for(int j = w; j >= u[i]; j–){ dp[j] = max(dp[j], dp[j - u[i]] + v[i]); ans = max(ans, dp[j]); } } printf(“%d\n”, ans); return 0; }

二 完全背包问题

题目链接：（https://www.acwing.com/problem/content/3/）

题目大意：有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 Ci ，价值是 Wi 。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

回忆 0-1 背包的就地滚动

回想 0-1 背包就地滚动时错误的代码，之所以错误，是因为每件物品重复使用多次，这恰好符合本题的要求！

递推求解

#include <bits/stdc++.h> using namespace std; #define N 2123 #define ll long long int dp[N], u[N], v[N]; int main() { ios::sync_with_stdio(0); int n, w, ans = 0; cin >> n >> w; for(int i = 1; i <= n; i++){ cin >> u[i] >> v[i]; } for(int i = 1; i <= n; i++){ for(int j = u[i]; j <= w; j++){ dp[j] = max(dp[j], dp[j - u[i]] + v[i]); ans = max(ans, dp[j]); } } printf(“%d\n”, ans); return 0; }

三 多重背包

题目链接：（https://www.acwing.com/problem/content/3/）

题目大意：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

问题的转化

对于本题，我们可以将其拆解为 0-1 背包问题解决

如何优化

#include<bits/stdc++.h> using namespace std; int main() { int N,V,v[1001],w[1001],dp[2001],s[1001] int a[25000],b[25000]; //2的12次方大于2000，也就是说一个数最多可以拆成12个，故数组容量乘12 cin>>N>>V; memset(dp,0,sizeof(dp)); for(int i=0;i<N;i++) cin>>v[i]>>w[i]>>s[i]; int total=0; for(int i=0;i<N;i++) { for(int j=1;j<s[i];j<<=1)//二进制拆分 { a[total]=jw[i];//存价值 b[total++]=jv[i];//存容量 s[i]-=j; } if(s[i])//当s[i]>0; { a[total]=s[i]w[i]; b[total++]=s[i]v[i]; } } for(int i=0;i<total;i++)//01背包 for(int j=V;j>=b[i];j–) dp[j]=max(dp[j],dp[j-b[i]]+a[i]); cout<<dp[V]; return 0; }

四 参考资料

博客：动态规划快速入门：https://www.jianshu.com/p/4dd4717301dc

题目：AcWing题库

参考课件：背包九讲（崔添翼）

​ nwpu2014暑假集训：动态规划2——简单背包问题（dsy）