重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
动态规划——01背包问题-创新互联
01背包问题：
本文名称：动态规划——01背包问题-创新互联
标题链接：http://cqcxhl.com/article/ipjoi.html
给定一个有一定容量的背包，和n个物品，每个物品只能选择一次。
每个物品有其对应的体积和价值。
问背包最多能装下的物品的大价值为多少。
输入格式：
第一行两个整数，N，V，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi 用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式：
输出一个整数，表示大价值。
思路：假设f[i][j]代表当只选择前n个物品并且背包容量只有j的时候所能装下物品的大价值
f[i][j] = max(f[i - 1][j]，f[i - 1][j - v[j]] + w[j])题目的答案就是f[n][m]。
为什么这样做是正确的呢：
当我们在面对第i件物品的时候，我们一定会在选择第i件物品和不选择第i件物品这两种情况中做出选择。
集合的角度：
假设我们有一个集合，集合表示的是只看前i件物品，背包容量为j的时候的所有物品选法，f[i][j]取集合中的大值，该集合可以划分为选择第i件物品和不选择第i件物品两个集合，f[i][j]取两个集合中的大值即可。
选和不选两种情况下状态的改变：
如果我们不选择第i件物品，那么我们的背包的价值就不变，等于f[i-1][j]。
如果我们背包的容量足够，我们选择第i件物品的话，虽然我们得到了第i件物品的价值，但是我们背包的体积一定会损耗，体积如果损耗，那么我们就有可能放下前面已经装进背包中的物品，此时我们的背包价值是不一定增大的。
所以我们的f[i][j]取两者的大值，也就是
f[i][j] = max(f[i - 1][j]，f[i - 1][j - v[j]] + w[j])给出图示：
代码如下：
#includeusing namespace std;
const int N = 1010;
int v[N], w[N];//每个物品的体积和价值
int f[N][N];//每个状态的大价值
int n, V;//物品数和背包容量
int main() {
cin >>n >>V;
for (int i = 1; i<= n; i++)
cin >>v[i] >>w[i];
for (int i = 1; i<= n; i++)
for (int j = 0; j<= V; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i])f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout<< f[n][V];
return 0;
} 我们发现，我们在更新的时候只会用到两层状态，每一个状态都是由上一层左边的状态推导而来的，我们不妨将这两行合并。
dp方程为：
f[j] = max(f[j], f[j - v] + w)一维状态中，f[j]默认就是上一层的f[j]，所以不用进行不选第i个物品的更新。当我们选择第i个物品时当，我们需要用到上一层左边的状态，所以我们不能把本层左边的状态更新成上一层左边的状态。如果我们从前往后进行更新，那么上一层的左边的状态就被更新掉了。所以我们应该从后往前更新。
代码如下：
#includeusing namespace std;
const int N = 1010;
int n, V;//物品数
int v, w;//总体积
int f[N];//状态
int main() {
cin >>n >>V;
for (int i = 0; i< n; i++) {
cin >>v >>w;
for (int j = V; j >= v; j--)
if (v<= j)f[j] = max(f[j - v] + w, f[j]);//f[j]默认就是上一行的值,所以不用更新v小于j的情况
}
cout<< f[V];
return 0;
} 注意：
1.背包问题中的状态，无论是一维还是二维，dp数组要同时满足背包体积和物品数量两个边界，而不是满足数量边界即可。
2.状态更新要用到f[i-1]，所以物品下标要从1开始。
例题： 装箱问题：有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。
在 n 个物品中，任选若干个装入箱内，使箱子的剩余空间为最小。
输入格式：
第一行是一个整数 V，表示箱子容量(0≤V小于等于20000)。
第二行是一个整数 n，表示物品数(0≤n≤30)。
接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。
思路：
题目要尽可能的装满箱子。我们给每个物品赋予一个价属性，价值的值就是体积的值。所以就是求一定体积下的大价值是多少。
代码如下：
//二维
#includeusing namespace std;
const int N = 20010, M = 40;
int f[M][N];
int n, m;//物品数和背包容量
int main() {
cin >>m >>n;
int v, w;
for (int i = 1; i<= n; i++) {//前i个物品
//读入体积和价值
cin >>v;
w = v;
for (int j = 0; j<= m; j++) {//体积为j
f[i][j] = f[i - 1][j];//不选该物品
if (j >= v)f[i][j] = max(f[i][j], f[i - 1][j - v] + w);
}
}
cout<< m - f[n][m];//记得做减法
return 0;
}
//一维
#includeusing namespace std;
const int N = 20010;
int f[N];
int n, m;//物品数和背包容量
int main() {
cin >>m >>n;
int v, w;
for (int i = 1; i<= n; i++) {//前i个物品
//读入体积和价值
cin >>v;
w = v;
for (int j = m; j >= v; j--) {//从后往前更新
f[j] = max(f[j], f[j - v] + w);
}
}
cout<< m - f[m];//记得做减法
return 0;
}
注意:最后输出的是剩余多少空间，我们求出来的是大体积，所以不要忘记做减法。
数字组合：给定 N 个正整数，从中选出若干个数，使它们的和为 M，求有多少种选择方案。
输入格式
第一行包含两个整数 N 和 M（1≤N≤100，1≤M≤10000）。
第二行包含 N 个整数，表示 A1,A2,…,AN。
输出格式：
包含一个整数，表示可选方案数。
思路：
f[i][j]表示只看前i个物品，和为j的情况。
如果选择第i个物品：f[i][j] = f[i-1][j-v[i]]。
如果不选第i个物品：f[i][j] = f[i-1][j]。
f[i][j]等于两者之和。
该题需要初始化，f[0][0] = 1。
代码如下：
//二维
#includeusing namespace std;
const int N = 110, M = 10010;
int f[N][M];
int n, m;//n个数和为m
int main() {
cin >>n >>m;
int v;
f[0][0] = 1;
for (int i = 1; i<= n; i++) {//前i个数
cin >>v;
for (int j = 0; j<= m; j++) {
f[i][j] += f[i - 1][j];//不选
if (j >= v)f[i][j] += f[i - 1][j - v];//选
}
}
cout<< f[n][m];
return 0;
}
//一维
#includeusing namespace std;
const int M = 10010;
int f[M];
int n, m;//n个数和为m
int main() {
cin >>n >>m;
int v;
f[0] = 1;//初始化
for (int i = 1; i<= n; i++) {//前i个数
cin >>v;
for (int j = m; j >= v; j--)
f[j] += f[j - v];//选
}
cout<< f[m];
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文名称：动态规划——01背包问题-创新互联
标题链接：http://cqcxhl.com/article/ipjoi.html