AcWing 2. 01背包问题(01背包)
2022/4/21 23:17:56
本文主要是介绍AcWing 2. 01背包问题(01背包),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
题目模型
- 01背包:每个物品只能选或不选
- 集合表示:f(i,j)
- 集合含义:所有从前i个物品中选,且总体积不超过j的所有选法
- 集合属性:max
- 集合划分:
题目代码
朴素版本
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N][N]; int main() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++ ) for(int j = 0; j <= m; j ++ ) { f[i][j] = f[i - 1][j]; if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; }
优化版本
#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N]; int main() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++ ) for(int j = m; j >= v[i]; j -- ) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0; }
这篇关于AcWing 2. 01背包问题(01背包)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置