Acwing背包题库
文章目录
一.01背包问题
问题描述
有 N 件物品和一个容量是 VV 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
题解：
首先DP问题分为俩个步骤：
1.状态表示：首先考虑用几维的状态表示，然后考虑集合的含义，以及其属性(求Max, Min,数量等)
2.状态计算：DP问题一般都可以将大问题划分为小问题，从小问题下手，从而得到一般的状态转移方程
对于这道题，我们考虑：
1.首先声明一个数组**F(i, j)**表示选前 i 件物品，且背包容量为 j 时所能获得的最大价值 。
2.对于每个物品我们有拿或者不拿俩种选择：
(1).j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿
(2).j >= w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。
如果拿取，则F(i, j) = f(i – 1, j – v[i]) + w[i],即 F(i, j) 表示在上一状态中选了第i件物品，
如果不拿，则F(i, j) = f(i – 1, j)
拿或者不拿，就要看哪种方法得到的价值最大，即
F(i, j) = max(f(i – 1, j), f(i – 1, j – v[i]) + w[i])
代码如下：
#include<bits/stdc++.h>
#define maxn 1000
using namespace std;
int v[maxn + 5], w[maxn + 5];
int dp[maxn + 5][maxn + 5];
int main()
{
int n,W;
scanf("%d%d",&n,&W);
for(int i = 0; i < n; i++)
scanf("%d%d",&v[i],&w[i]);
for(int i = 0; i < n; i++){
for(int j = 0; j <= W; j++){
if(v[i] > j)dp[i + 1][j] = dp[i][j];
else dp[i + 1][j] = max(dp[i][j], dp[i][j - v[i]] +w[i]);
}
}
printf("%d\n",dp[n][W]);
return 0;
}
01背包问题一维数组实现
状态转移方程如果是由上一层的状态得来的话，枚举体积的时候从大到小枚举，这样我们计算体积的时候，可以保证本层所用到的体积还没有被计算过
如果用的是本层的状态，枚举体积的时候就要从小到大枚举，这样我们计算体积的时候，可以保证所用到的体积是本层之前计算好的体积
#include<iostream>
using namespace std;
const int N = 1010;
int d[N];
int main()
{
int n, V;
cin >> n >> V;
for(int i = 0; i < n; i++){
int v, w;
cin >> v >> w;
for(int j = V; j >= v; j--)
d[j] = max(d[j], d[j - v] + w);
}
cout << d[V] << endl;
return 0;
}
二.01背包问题2
问题描述
有n个重量和价值分别为wi，vi的物品。从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和最大的方案
输入样例
4 5
2 1 3 2
3 2 4 2
输出样例
7
取值范围
1<=n<=100
1<=wi<=10^7
1<=vi<=100
1<=W<=10 ^9
分析：
这里与背包问题1不同的地方是修改了限制的条件，求解这一问题的复杂度是O（NW），对于这一问题的规模来讲就不够用了，相比较重量来说，价值的范围较小一些，所以可以改变DP的对象，背包问题1用DP来表示不同体积下的最大价值，这次我们不妨用DP来表示不同价值下的最小体积。
定义：F(i, j)表示前i个物品挑选出价值总和为j时的最小重量,(不存在是就是一个充分大的数INF)由于前0个物品都挑选不了 所以F(0, 0)=0, F(0, j)=INF
状态转移式为：F(i, j) = min(f(i – 1, j), F(i – 1,j – w[i]) + v[i])
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INF 1000000000
#define max_n 100
#define max_v 100
using namespace std;
int n,W;
int dp[max_n+5][max_n*max_v+5];
int w[max_n+5],v[max_n+5];
void solve()
{
for(int i=0;i<n;i++){
for(int j=0;j<=max_n*max_v+5;j++){
if(j<v[i])dp[i+1][j]=dp[i][j];
else dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);
}
}
}
int main()
{
scanf("%d%d",&n,&W);
for(int i=0;i<n;i++)
scanf("%d",&w[i]);
for(int i=0;i<n;i++)
scanf("%d",&v[i]);
fill(dp[0],dp[0]+max_n*max_v+5,INF); //初始化
dp[0][0]=0;
solve();
int res=0;
for(int i=0;i<=max_n*max_v;i++){
if(dp[n][i]<=W)res=i;
}
printf("%d\n",res);
return 0;
}
三.完全背包问题
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
题解：
完全背包问题，物品有无限个，这里我们来考虑第i个物品选多少个
1.对于每种物品，我们有选和不选俩种选择，
如果不选，F(i + 1 ,j) = F(i , j)
如果选了，我们还要考虑选多少个，即F(i + 1, j) = max(F(i + 1, j – v[i]) + w[i], F(i + 1, j))
取俩种情况的最大值，变得到了状态转移方程：
F(i + 1, j) = max(F(i , j), F(i + 1, j – v[i]) + w[i])
代码如下：
#include<bits/stdc++.h>
#define maxn 1000
using namespace std;
int v[maxn + 5], w[maxn + 5];
int dp[maxn + 5][maxn + 5];
int main()
{
int n,V;
scanf("%d%d",&n,&V);
for(int i = 0; i < n; i++)
scanf("%d%d",&v[i],&w[i]);
for(int i = 0; i < n; i++){
for(int j = 0; j <= V; j++){
if(v[i] > j)dp[i + 1][j] = dp[i][j];
else dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
}
}
printf("%d\n",dp[n][V]);
return 0;
}
一维数组实现
上面我们说到：如果用的是本层的状态，枚举体积的时候就要从小到大枚举即可，这样我们计算体积的时候，可以保证所用到的体积是本层之前计算好的体积
代码如下：
#include<iostream>
using namespace std;
const int N = 1010;
int d[N];
int main()
{
int n,V;
cin >> n >> V;
for(int i = 0; i < n; i++){
int v, w;
cin >> v >> w;
for(int j = v; j <= V; j++)
d[j] = max(d[j], d[j - v] + w);
}
cout << d[V] << endl;
return 0;
}
四.多重背包问题 I
题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
题解：
当成01背包问题来做即可，在枚举体积的时候在枚举一下该物品个数
状态转移方程：F(i, j) = max(F(i – 1, j), F(i – 1, j – k * v[i]) + k * w[i])
一维数组实现，由于该状态转移用的是上一层的状态，所以枚举体积的时候，我们从大到小枚举，代码如下：
#include<iostream>
using namespace std;
const int N = 110;
int d[N];
int main()
{
int n, V;
cin >> n >> V;
for(int i = 0; i < n; i++){
int v, w, s;
cin >> v >> w >> s;
for(int j = V; j >= v; j--)
for(int k = 1; k <= s && k * v <= j; k++)
d[j] = max(d[j], d[j - k * v] + k * w);
}
cout << d[V] << endl;
return 0;
}
五.多重背包问题II
题目描述
有 N 种物品和一个容量是 V 的背包
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示：
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
题解：
由于这题的数据范围有点大，直接暴力枚举会超时，那么我们就要想一个可以优化的方法，这里主要是对物品的个数进行拆分，将其变为01背包问题
二进制拆分法： 我们知道，从2^0, 2^1, 22…2(k – 1)这k个数中选出任意个相加可以表示出0~2^k之间任何整数，所以我们可以对每一种物品就行二进制拆分，将其转化为01背包问题
代码如下：
#include<iostream>
using namespace std;
const int N = 1e6 + 9;
int a[N], b[N], d[N];
int main()
{
int k = 0;
int n, V;
cin >> n >> V;
for(int i = 0; i < n; i++){
int v, w, s;
scanf("%d%d%d", &v, &w, &s);
for(int j = 1; j <= s; j <<= 1){
//二进制拆分
a[k] = j * v; //用a数组来存体积
b[k++] = j * w; //b数组来存价值
s -= j;
}
if(s > 0){
a[k] = s * v;
b[k++] = s * w;
}
}
for(int i = 0; i < k; i++)//01背包
for(int j = V; j >= a[i]; j--)
d[j] = max(d[j], d[j - a[i]] + b[i]);
cout << d[V] << endl;
return 0;
}
六.分组背包问题
题目描述
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例
8
题解：
跟完全背包问题类似
用F(i, j)来表示选前i组物品且体积为j时的价值最大值，我们先枚举每一组，由于F(i, j)的状态用的是上一层的状态，所以我们枚举体积的时候从大到小来枚举，再依次枚举每一组里的物品，找到体积为j时，选取i组中哪个物品的价值最大
代码如下：
#include<iostream>
using namespace std;
const int N = 110;
int v[N][N], w[N][N];
int d[N], s[N];
int main()
{
int n, V;
cin >> n >> V;
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 = V; j >= 0; j--) //枚举体积
for(int k = 0; k < s[i]; k++)//枚举第i组体积为j时，选取哪个物品价值最大
if(v[i][k] <= j)
d[j] = max(d[j], d[j - v[i][k]] + w[i][k]);
cout << d[V] << endl;
return 0;
}
七.背包问题求方案数
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示 方案数 模 109+7 的结果。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
2
**题解：**在01背包问题的基础上，添加一个num数组用来记录方案数即可
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, mod = 1000000007;
int w[N], v[N], dp[N], num[N];
int main()
{
int n, V;
scanf("%d%d", &n, &V);
for(int i = 0; i < n; i++){
scanf("%d%d", &v[i], &w[i]);
num[i] = 1;
}
for(int i = 0; i < n; i++){
for(int j = V; j >= v[i]; j--){
if(dp[j] < dp[j - v[i]] + w[i]){
//更新最大价值
dp[j] = dp[j - v[i]] + w[i];
num[j] = num[j - v[i]] % mod;//num数组记录更新方案数
}
else if(dp[j] == dp[j - v[i]] + w[i]){
//如果相等
num[j] = (num[j] + num[j - v[i]]) % mod;//方案数相加
}
}
}
cout << num[V] << endl;
return 0;
}
八. 背包问题求具体方案
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
物品编号范围是 1…N。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
1 4
#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], d[N][N], ans[N];
int n, m;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for(int i = n; i >= 1; i--){
for(int j = 0; j <= m; j++){
d[i][j] = d[i + 1][j];
if(j >= v[i])
d[i][j] = max(d[i][j], d[i + 1][j - v[i]] + w[i]);
}
}
int j = m;
for(int i = 1; i <= n; i++){
if(j >= v[i] && d[i][j] == d[i + 1][j - v[i]] + w[i]){
cout << i << ' ';
j -= v[i];
}
}
return 0;
}
今天的文章背包九讲问题——超详细分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：http://bianchenghao.cn/6988.html
