在《Harry Potter and the Deathly Hallows》中,Harry Potter他们一起逃亡,现在有许多的东西要放到赫敏的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品,现在给出该种物品的数量、体积、价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,赫敏会非常地感谢你。
【输入文件】(hallows.in)
(1)第一行有2个整数,物品种数n和背包装载体积v。
(2)2行到i+1行每行3个整数,为第i种物品的数量m、体积w、价值s。.
【输出文件】(hallows.out)
输出文件hallows.out仅包含一个整数,即为能拿到的最大的物品价值总和。
【输入样例】
2 10
3 4 3
2 2 5
【输出样例】
13
【注释】
选第一种一个,第二种两个。
结果为3*1+5*2=13
【数据规模】
对于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
逃亡的准备这道题怎么做,给代码(C++)
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- CSDN专家-深度学习进阶 2021-08-29 09:31关注
#include<iostream> #include<cstdio> using namespace std; int q,dp[510],x,y,z,n,s=0; void ddp(int xx,int yy)//即时背包 { for(int i=n;i>=xx;i--)dp[i]=max(dp[i],dp[i-xx]+yy); return; } int main() { scanf("%d%d",&q,&n); while(q--) { scanf("%d%d%d",&x,&y,&z); s=1;//位的价值 while(x>=s)//二进制拆分 { ddp(s*y,s*z); x-=s; s*=2; } if(x!=0)ddp(x*y,x*z); } printf("%d",dp[n]); return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决评论 打赏 举报无用 2
悬赏问题
- ¥20 软件测试决策法疑问求解答
- ¥15 win11 23H2删除推荐的项目,支持注册表等
- ¥15 matlab 用yalmip搭建模型,cplex求解,线性化处理的方法
- ¥15 qt6.6.3 基于百度云的语音识别 不会改
- ¥15 关于#目标检测#的问题:大概就是类似后台自动检测某下架商品的库存,在他监测到该商品上架并且可以购买的瞬间点击立即购买下单
- ¥15 神经网络怎么把隐含层变量融合到损失函数中?
- ¥15 lingo18勾选global solver求解使用的算法
- ¥15 全部备份安卓app数据包括密码,可以复制到另一手机上运行
- ¥20 测距传感器数据手册i2c
- ¥15 RPA正常跑,cmd输入cookies跑不出来