01背包问题(动态规划)
2022/4/14 6:19:18
本文主要是介绍01背包问题(动态规划),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2. 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
二维数组解法:
1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 5 using namespace std; 6 constexpr int N = 1010; 7 int main() { 8 int n = 0; // 物品个数 9 int v = 0; // 背包容量 10 // 输入物品个数和背包容量 11 std::cin >> n >> v; 12 vector<int> volume(N, 0); // 存储每件物品的体积 13 vector<int> weight(N, 0); // 存储每件物品的价值 14 // 输入每件物品的体积和价值 15 for (int i = 1; i <= n; i++) { 16 std::cin >> volume[i] >> weight[i]; 17 } 18 vector<vector<int>> dp(N, vector<int>(N, 0)); 19 // dp[i][j] 前i件物品放进当前背包容量为j的背包里装的物品最大总价值 20 for (int i = 1; i <= n; i++) { 21 for (int j = 1; j <= v; j++) { 22 // 第i件物品不选时 23 dp[i][j] = dp[i - 1][j]; 24 // 第i件物品选时(j >= volume时说明当前背包容量可以装的下第i件物品) 25 if (j >= volume[i]) { 26 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volume[i]] + weight[i]); 27 } 28 } 29 } 30 31 std::cout << dp[n][v] << endl; 32 return 0; 33 }
一维数组解法:
1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 5 using namespace std; 6 constexpr int N = 1010; 7 int main() { 8 int n = 0; // 物品个数 9 int v = 0; // 背包容量 10 // 输入物品个数和背包容量 11 std::cin >> n >> v; 12 vector<int> volume(N, 0); // 存储每件物品的体积 13 vector<int> weight(N, 0); // 存储每件物品的价值 14 // 输入每件物品的体积和价值 15 for (int i = 1; i <= n; i++) { 16 std::cin >> volume[i] >> weight[i]; 17 } 18 vector<int> dp(N, 0); 19 // dp[i]当前背包容量为i的背包里装的物品的最大总价值 20 for (int i = 1; i <= n; i++) { 21 for (int j = v; j >= volume[i]; j--) { 22 // 第i件物品不选和选择取最大值 23 dp[j] = max(dp[j], dp[j - volume[i]] + weight[i]); 24 } 25 } 26 27 std::cout << dp[v] << endl; 28 return 0; 29 }
这篇关于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动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南