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——————
———————感谢您的阅读—————————
