动态规划01背包问题求解(附c/cpp代码)
1. 问题描述
有 n 种物品和一个容量是 y 的背包,每种物品只有一件。
第 i 种物品的体积是 wi,价值是 vi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值和物品序号。
2. 输入格式
第一行两个整数,N,Y,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数wi,vi,用逗号隔开,分别表示第 i 种物品的体积和价值。
3. 输出格式
输出最大价值,物品序列号。
4. 输入样例
3,10
5,8
8,20
4,17
5. 输出样例
最大价值:25
物品序号:3号 1号
6. 问题分析
7. 代码实现
#include <iostream>
#include <bits/stdc .h>
using namespace std;
typedef struct {
int w;
int v;
}Object;
int main(){
int n,y;
char ch;
cin>>n>>ch>>y;
Object ob[n 1];
for(int i=1;i<=n; i)
cin>>ob[i].w>>ch>>ob[i].v;//ob[0]未使用
int arr[n 1][y 1];
for(int i=0;i<y 1; i)
arr[0][i] = 0;
for(int i=0;i<n 1; i)
arr[i][0] = 0;
for(int i=1;i<n 1; i)
for(int j=1;j<y 1; j){
arr[i][j] = arr[i-1][j];
if(ob[i].w <= j)
arr[i][j] = max(arr[i-1][j],arr[i-1][j-ob[i].w] ob[i].v);
}
vector <int> r;
int j = y;
for(int i=n;i>0;--i)
if (arr[i][j] != arr[i-1][j]){
r.push_back(i);
j = j - ob[i].w;
}
cout<<"最大价值:"<<arr[n][y]<<endl<<"物品序号:";
for(vector<int>::iterator it = r.begin();it!=r.end(); it)
cout<<*it<<"号 ";
return 0;
}
8. 执行结果
10,30
2,3
5,6
8,6
10,12
6,7
9,11
4,7
6,8
7,8
5,8
最大价值:41
物品序号:10号 7号 6号 4号 1号
Process returned 0 (0x0) execution time : 1.365 s
Press any key to continue.
——————END-2022-04-23——————
———————感谢您的阅读—————————
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbffg
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01