[动态规划] 背包九问

2023-11-03 03:10
文章标签 动态 规划 背包 九问

本文主要是介绍[动态规划] 背包九问，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

背包九问
下面是各个问题的模版题，对于代码，读者可在理解后，直接套用。

借鉴了dd大神的博客

1.01背包问题
2.完全背包问题
3.多重背包问题
4.混合背包问题
5.二维费用的背包问题
6.分组背包问题
7.背包问题求方案
8求背包问题的方案
9有依赖的背包问题

1.01背包问题

有 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
输出样例：
8

方法：从大到小枚举体积

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1001;int dp[maxn];
int n, m;int main () {cin >> n >> m;for (int i = 1; i <= n; i++) {int w, v;cin >> w >> v;for (int j = m; j >= w; j--) {dp[j] = max(dp[j], dp[j - w] + v);}}cout << dp[m];return 0;
}

2.完全背包问题

有 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
输出样例：
8
方法从小到大枚举体积

#include<iostream>
using namespace std;
const int maxn= 1001;
int dp[maxn];
int w[maxn], v1[maxn];
int main () {int n, v;cin >> n >> v;for (int i = 1; i <= n; i++) {cin >> w[i] >> v1[i];}for (int i = 1; i <= n; i++) {for (int j = w[i]; j <= v; j++) {dp[j] = max(dp[j], dp[j - w[i]] + v1[i]);}}cout << dp[v];return 0;
}

3.多重背包问题

有 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
根据数量，利用1 2 4 8。。。 拆分成01背包问题

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2001;int dp[maxn];
int n, m;
struct node {int w, v;
};
int main () {cin >> n >> m;vector<node> cp;for (int i = 1; i <= n; i++) {int w, v, s;cin >> w >> v >> s;for (int k = 1; k <= s; k *= 2) {s -= k;cp.push_back({w * k, v * k});}if (s > 0)cp.push_back({w * s, v * s});}vector<node>::iterator it = cp.begin();for (; it != cp.end(); it++) {for (int j = m; j >= it->w; j--) {dp[j] = max(dp[j], dp[j - it->w] + it->v);}}cout << dp[m];return 0;
}

4.混合背包问题

有 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 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8
把多重背包变成01背包，从大到小枚举体积，完全背包从小到大枚举体积。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1001;
int n, v;
int dp[maxn];
struct node {int kind;int w, v;
};
int main () {cin >> n >> v;vector<node> cp;for (int i = 1; i <= n; i++) {int w, v, s;cin >> w >> v >> s;if (s < 0) cp.push_back({-1, w, v});else if (s == 0) cp.push_back({0, w, v});else {for (int k = 1; k <= s; k *= 2) {s -= k;cp.push_back({-1, w * k, v * k});}if (s > 0) cp.push_back({-1, w * s, v * s});}}for (vector<node>::iterator it = cp.begin(); it != cp.end(); it++) {if (it->kind < 0) {for (int j = v; j >= it->w; j--) {dp[j] = max(dp[j], dp[j - it->w] + it->v);}} else {for (int j = it->w; j <= v; j++) {dp[j] = max(dp[j], dp[j - it->w] + it->v);}}}cout << dp[v];return 0;
}

5.二维费用的背包问题

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例：
8
将背包的体积和重量构造成一个二维的数组，这题是一个01背包，所以从大到小枚举体积。

#include<bits/stdc++.h>
using namespace std;int dp[101][101];
int n, m, v;int main () {cin >> n >> v >> m; // for(int i = 1; i <= n; i++) {int a, b, c;cin >> a >> b >> c;for (int j = v; j >= a; j--) {for (int z = m; z >= b; z--) {dp[j][z] = max(dp[j][z], dp[j - a][z - b] + c);}}}cout << dp[v][m];return 0;
}

6.分组 背包问题

有 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
在01背包的基础上，进行决策，选每一组的第i个，求max

#include<bits/stdc++.h>
using  namespace std;const int maxn = 101;int dp[maxn], v1[maxn], w[maxn];int n, v;
int  main () {cin >> n >> v;for (int i = 1; i <= n; i++) {int t;cin >> t;for (int j = 1; j <= t; j++)    cin >> v1[j] >> w[j];for (int j = v; j >= 0;j--) {for (int k = 1; k <= t; k++) {if (j >= v1[k])dp[j] = max(dp[j], dp[j - v1[k]] + w[k]);}}}cout << dp[v];return 0;
}

9有依赖的背包问题

有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
如下图所示：
在这里插入图片描述

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。
每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。
接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。
输出格式
输出一个整数，表示最大价值。
数据范围
1≤N,V≤100
1≤vi,wi≤100
父节点编号范围：
内部结点：1≤pi≤N;
根节点 pi=−1;
输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例：
11
树形dp+分组背包

#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;
}

这篇关于[动态规划] 背包九问的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/335176。

相关文章

如何用Python绘制简易动态圣诞树

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码：效果：总结 代码：import randomimport timefrom math
阅读更多...
Java中JSON字符串反序列化(动态泛型)

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求：定时任务扫描，反射调用目标对象，但是，方法的传参不是固定的。方案一：将方法参数存成jsON字
阅读更多...
.NET利用C#字节流动态操作Excel文件

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
poj2576(二维背包)

poj2576(二维背包)

题意：n个人分成两组，两组人数只差小于1 ， 并且体重只差最小 对于人数要求恰好装满，对于体重要求尽量多，一开始没做出来，看了下解题，按照自己的感觉写，然后a了 状态转移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数，j表示背包容量，k表示输入的体重的 代码如下： #include<iostream>#include<
阅读更多...
hdu2159（二维背包）

hdu2159（二维背包）

这是我的第一道二维背包题，没想到自己一下子就A了，但是代码写的比较乱，下面的代码是我有重新修改的 状态转移：dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示，打了i个怪物，消耗j的耐力值，所得到的最大经验值 代码如下： #include<iostream>#include<algorithm>#include<
阅读更多...
csu(背包的变形题)

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物，m个人，每个人的魔法消耗和魔法伤害不同，求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近 可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v） 其中指数为价值，每一项的数目为（该物品数+1）个 代码如下： #include<iostream>#include<algorithm>
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2