首页 > 代码库 > rqnoj 逃亡的准备
rqnoj 逃亡的准备
题目描述
【问题描述】
在《Harry Potter and the Deathly Hallows》中,Harry Potter他们一起逃亡,现在有许多的东西要放到赫敏的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品,现在给出该种物品的数量、体积、价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,赫敏会非常地感谢你。
出自:宜昌一中
【数据规模】
对于30%的数据
1<=v<=500
1<=n<=2000
1<=m<=10
1<=w<=20
1<=s<=100
对于100%的数据
1<=v<=500
1<=n<=2000
1<=m<=5000
1<=w<=20
1<=s<=100
输入格式
【输入】
(1)第一行有2个整数,物品种数n和背包装载体积v。
(2)2行到n+1行每行3个整数,为第i种物品的数量m、体积w、价值s。.
输出格式
【输出】
仅包含一个整数,即为能拿到的最大的物品价值总和。
样例输入
样例输出
注释
样例解释:选第一种一个,第二种两个。
提交题目 Error [ 更改语言 ] Language
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cstdlib>#include<cmath>#include<algorithm>#include<queue>#include<vector>using namespace std;int n,v,f[2010];int main(){ scanf("%d%d",&n,&v); for(int i=1;i<=n;i++) { bool flag=false; int m,w,s; scanf("%d%d%d",&m,&w,&s); for(int i=1;i<=m;i++) { for(int j=v;j>=w;j--) if(f[j-w]+s>f[j]) { f[j]=f[j-w]+s; flag=true;//优化 } if(!flag) break; } } printf("%d\n",f[v]); return 0;}
rqnoj 逃亡的准备
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。