0
已解决
资深守护
2856 奖品选择
题目描述 Description
小明参加一个活动，到了奖励环节，可以选择奖品。假设现在有n个奖品，每奖品占的体积均为2，第i个奖品有一个价值为ai。现在他带着一个大包，体积为V。如果他想得到的奖品的价值总和尽可能大，请问他能获得的最大价值是多少？
输入描述 Input Description
第一行，两个整数，n V，n表示奖品个数，V表示包的体积
接下来一行，n个整数，第i个整数ai表示第i件奖品的价值
输出描述 Output Description
能得到的最大价值
样例输入 Sample Input
3 5
8 5 9
样例输出 Sample Output
17
数据范围及提示 Data Size & Hint
3≤n≤100
4≤V≤200
0
已采纳
高级守护
我是用桶写的:
以下是核心：
......
int a[100];
定义数组
......
int n,v,c,cnt=0,t,d=0;
定义变量
cin>>n>>v;
c=v/2;
c是体积
for(int i=1;i<=n;i++){
cin>>t;
a[t]++;
}
输入桶
for(int i=100;i>=1;i--)
倒着遍历通，求最大的值
for(int j=1;j<=a[i];j++){
到这都是遍历桶
if(d<c){
cnt+=i;
d++;
}
这是我加的判断，d是计数用的最大值的数量不能超过体积，cnt是最大值的和
}
cout<<cnt;
输出
徐硕在2020-04-21 22:39:36追加了内容
不知道你有没有学，所以我把代码的意思都写在下面了，祝你AC。
徐硕在2020-04-21 22:43:54追加了内容
你也可以看看我楼上的，他的思路和我一样，都是用排序找到最大的数，然后求和。他写的比我简单，好理解
0
资深光能
01背包
f[i][j]:前i物品容量为j，能获得的最大价值
0
中级守护
从小到大排序
核心代码：
for(int i=0;i<n;i++)
cin>>jiang[i];
sort(jiang,jiang+n);
for(int i=0;i<V/2;i++)
jia+=jiang[n-1-i];
cout<<jia;
0
初级天翼
01背包模板题
