背包问题求具体方案(动态规划)
2022/4/16 6:14:10
本文主要是介绍背包问题求具体方案(动态规划),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
背包问题求具体方案有 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
解题思路(见代码注释):
1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 5 using namespace std; 6 7 constexpr int N = 1010; 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 19 vector<vector<int>> dp(N, vector<int>(N, 0)); // dp[i][j]表示从第i个物品到最后一个物品,装入容量为j的背包的最优解 20 vector<goods> goodsList(N, {0}); 21 for (int i = 1; i <= n; i++) { 22 std::cin >> goodsList[i].volume >> goodsList[i].weight; // 输入每个物品的体积和价值 23 } 24 for (int i = n; i >= 1; i--) { 25 for (int j = 1; j <= v; j++) { 26 dp[i][j] = dp[i + 1][j]; // 不选物品i 27 if (j >= goodsList[i].volume) { // 选和不选第i件物品时取最大值 28 dp[i][j] = max(dp[i][j], dp[i + 1][j - goodsList[i].volume] + goodsList[i].weight); 29 } 30 } 31 } 32 // 经过上面的逆序取物的01背包操作后,我们让最优解落到了dp[1][m]中 33 // 因此当我们从第一个物品开始出发去找最优解的路径时,那么此时背包容量应该为j 34 int j = v; // 背包的剩余容量 35 // 去寻找最优解的路径 36 for (int i = 1; i <= n; i++) { 37 // 若dp[i][j]能通过dp[i+1][j-goodsList[i].volume]得到,则一定要选第i个物品 38 if (j >= goodsList[i].volume && dp[i][j] == dp[i + 1][j - goodsList[i].volume] + goodsList[i].weight) { 39 std::cout << i << " "; 40 // 由于选择的是这件物品,因此背包的剩余质量就是j-v[i] 41 j -= goodsList[i].volume; 42 } 43 } 44 cout << endl; 45 return 0; 46 }
这篇关于背包问题求具体方案(动态规划)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南