背包问题总结
Index
01背包
题目描述：有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
思路：动态规划，对于每一件物品遍历背包容量，当背包可容纳值大于等于当前物品，与之前已放进去的物品所得价值进行对比，考虑把是否需要置换。
状态转移方程：定义dp[i][j]：前i个物品，背包容量j下的最优解
- （1）当前背包容量不够，为前𝑖−1个物品最优解：j< w[i]时，有
dp[i][j] = dp[i-1][j]- （2）当前背包容量够，判断选还是不选第i个物品：j >= w[i]时， 选该物品:
dp[i][j] = dp[i-1][j-w[i]] + v[i]不选该物品:dp[i][j]=dp[i-1][j]
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i])
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
int ans = 0;
for (int i = 0; i <= m; ++j)
ans = max(ans, dp[n][i])
一维优化
for (int i = 1; i <= n; ++i) {
for (int j = m; j >= v[i]; --j)
dp[j] = max(dp[i], dp[j - v[i]] + w[i]);
}
// 最大价值为f[m]
体积恰好为m的最大价值
- 修改初始化策略。dp[0] = 0, dp[i] = INT_MIN, i != 0
体积很大时的01背包
n个物品，每个物品有价值w，体积v，在总体积不超过V，条件下，能装物品的最大价值是多少。
- 1 <= V <= 1e9
- 1 <= n <= 100
- 1 <= w <= 1e3
分析
本题体积范围较大，直接定义体积为 dp[i][j] 为前i个物品，体积不超过j时的最大价值，时间和空间都无法承受。
但是本题的w较小，可以定义 dp[i][j] 为 前i个物品，价值为j时的最小体积。
int maxValue(vector<int> &w, vector<int> &v,int V) {
vector<long long> dp(100010, 1e18);
dp[0] = 0;
for (int i = 0; i < n; ++i)
for (int j = 100000; j >= w[i]; --j)
dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
int ans = 0;
for (int i = 100000; i >= 0; --i)
if (dp[i] <= V) ans = max(ans, i);
return ans;
}
完全背包
- 题目描述：有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。第 i种物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
- 思路：
f[i] 表示体积为i的情况下，最大价值是多少 res = max(f[0,…,m])
for (int i = 1; i <= n; ++i) {
for (int j = v[i]; j <= m; ++j) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
完全背包输出方案
- 输入: 体积数组v，价值数组w，背包容量m。 _ 返回: bool数组cnt(下标0-n-1),cnt[i]表示第i个物品选了多少个。
vector<int> get_ans(vector<int> &v, vector<int> &w, int m) {
int n = v.size();
vector<int> f(m + 1), cnt(n);
vector p(n + 1, vector<bool>(m + 1));
for (int i = 0; i < n; ++i) {
for (int j = v[i]; j <= m; ++j) {
if (f[j] < f[j - v[i]] + w[i]) {
f[j] = f[j - v[i]] + w[i];
p[i + 1][j] = true;
}
}
}
for (int i = n, j = m; i > 0 && j > 0; ) {
if (p[i][j]) {
cnt[i - 1] ++;
j -= v[i - 1];
}else i--;
}
return cnt;
};
多重背包
题目描述：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本算法
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
| f[i][v]=max{f[i-1][v-kc[i]]+kw[i] | 0<=k<=n[i]} |
复杂度是O(V*Σn[i])。
转化为01背包问题
另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。
但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
for (int i = 0; i < n; ++i) {
for (int j = m; j >= 0; ++j) {
for (int k = 1; k <= n[i] && k * v[i] <= j; ++k)
f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
}
}
优化 二进制拆解
struct Good {
int v, w;
};
vector<Good> goods;
for (int i = 0; i < n; ++i)
{
for (int k = 1; k <= n[i]; k *= 2) {
n[i] -= k;
goods.push_back({v[i] * k, w[i] * k});
}
if (n[i] > 0) goods.push_back({v[i] * n[i], w[i] * n[i]});
}
for (auto good :goods) {
for (int j = m; j >= good.v; --j) {
f[j] = max(f[j], f[j - good.v] + good.w);
}
}
混合背包
有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
- 第一类物品只能用1次（01背包）；
- 第二类物品可以用无限次（完全背包）；
- 第三类物品最多只能用 si 次（多重背包）； 每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。
输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
si=−1 表示第 i 种物品只能用1次； si=0 表示第 i 种物品可以用无限次； si>0 表示第 i 种物品可以使用 si 次；
输出格式 输出一个整数，表示最大价值。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, f[N];
struct Thing {
int kind, v, w;
};
vector<Thing> things;
int main() {
cin >> n>>m;
for(int i = 0;i<n;i++) {
int v, w, s;
cin >> v >> w >> s;
if(s < 0) {
things.push_back({-1,v,w});
}else if(s == 0) things.push_back({0,v,w});
else{
for(int k = 1;k <= s; k*=2){
s -=k;
things.push_back({-1,v*k,w*k});
}
if(s > 0) things.push_back({-1,v*s,w*s});
}
}
for(auto thing:things) {
if(thing.kind < 0){
for(int j = m;j >= thing.v;j--)
f[j] = max(f[j],f[j-thing.v]+thing.w);
}else{
for(int j = thing.v;j <= m;j++)
f[j] = max(f[j],f[j-thing.v]+thing.w);
}
}
cout << f[m] << endl;
return 0;
}
二维费用的背包问题
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。 输出最大价值。
输入格式 第一行两个整数，N，V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。
输出格式 输出一个整数，表示最大价值。
#include<iostream>
using namespace std;
const int N=110;
int n,c,M;
int f[N][N];
int main(){
cin>>n>>c>>M;
for(int i=0;i<n;i++){
int v,m,w;
cin>>v>>m>>w;
for(int j=c;j>=v;j--)
for(int k=M;k>=m;k--)
f[j][k]=max(f[j][k],f[j-v][k-m]+w);
}
cout<<f[c][M]<<endl;
return 0;
}
分组背包
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式 第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量； 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值； 输出格式 输出一个整数，表示最大价值。
#include<iostream>
using namespace std;
const int N=110;
int f[N],s[N];
int v[N][N],w[N][N];
int n,m;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>s[i];
for(int j=0;j<s[i];j++){
cin>>v[i][j]>>w[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=m;j>0;j--){
for(int k=0;k<s[i];k++){
if(v[i][k]<=j){
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
}
cout<<f[m]<<endl;
return 0;
}
有依赖的背包问题
有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
如下图所示：
1
/ \
2 3
/ \
4 5
如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。
每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式 第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。
接下来有 N 行数据，每行数据表示一个物品。 第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。 如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。
输出格式 输出一个整数，表示最大价值。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int n, m;
int h[N], e[N], ne[N], idx;
int v[N], w[N];
int f[N][N];
void add(int x, int y) {
e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}
void dfs(int x) {
for (int i = h[x]; i != -1; i = ne[i]) {
int y = e[i];
dfs(y);
for (int j = m - v[x]; j >= 0; j--) {
for (int k = 0; k <= j; k++) {
f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
}
}
}
for (int i = m; i >= v[x]; i--) {
f[x][i] = f[x][i - v[x]] + w[x];
}
for (int i = 0; i < v[x]; i++) {
f[x][i] = 0;
}
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
int root;
for (int i = 1; i <= n; i++) {
int p;
cin >> v[i] >> w[i] >> p;
if (p == -1) {
root = i;
} else {
add(p, i);
}
}
dfs(root);
cout << f[root][m] << endl;
return 0;
}
