多重背包问题 II(动态规划)
2022/4/15 6:14:04
本文主要是介绍多重背包问题 II(动态规划),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
多重背包问题 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
解题思路:
N个物品,第 i 种物品最多有 si 件,所有物品按份划分后,可按照01背包问题求解
1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 5 using namespace std; 6 7 constexpr int N = 2010; 8 9 typedef struct { 10 int volume; 11 int weight; 12 } goods; // 物品(包含体积和价值) 13 14 int main() { 15 int n = 0; // 物品个数 16 int v = 0; // 背包容量 17 std::cin >> n >> v; // 输入物品的个数和背包容量 18 vector<goods> goodsList; 19 goodsList.clear(); 20 vector<int> dp(N, 0); 21 for (int i = 0; i < n; i++) { 22 int volume = 0; 23 int weight = 0; 24 int s = 0; 25 std::cin >> volume >> weight >> s; // 输入每件物品的体积、价值和最大可选择个数 26 // 物品分成log(s)份 27 for (int k = 1; k <= s; k *= 2) { 28 s -= k; 29 goodsList.push_back({k * volume, k * weight}); 30 31 } 32 // 如果物品分成log(s)份后还有剩余,剩下的物品凑成一份 33 if (s > 0) { 34 goodsList.push_back({s * volume, s * weight}); 35 } 36 } 37 // 按照01背包问题处理 38 for (auto goods : goodsList) { 39 for (int j = v; j >= goods.volume; j--) { 40 dp[j] = max(dp[j], dp[j - goods.volume] + goods.weight); 41 } 42 } 43 std::cout << dp[v] << endl; 44 return 0; 45 }
这篇关于多重背包问题 II(动态规划)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了