逃亡的准备 【问题描述】 在《Harry Potter and the Deathly Hallowsgprs天线》中,Harry Potter他们一起逃亡,现在有许多的东西要放到赫敏的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品,现在给出该种物品的数量、体积、价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,赫敏会非常地感谢你。 【输入文件】(hallows.in) (1)第一行有2个整数,物品种数n和背包装载体积v。 (2)2行到n+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 3ku1<=w<=20 1<=s<=100 加一个标记c剪枝 var t,i,j,q,ji,c,m,w,s,n,vv:longint; 锂电保护芯片a:array[0..500] of longint; begin assign(input,'1.txt'); reset(input); readln(n,vv); for i:=1 to n do begin readln(m,w,s); t:=vv-w;c:=1;ji:=0; for q:=1 to m do begin if c=0 then break; c:=0; for j:=t downto ji do if a[j]+s>a[j+w] then begin ji:=j;c:=1;a[j+w]:=a[j]+s;end; end; end; t:=0; for i:=0 to vv do if t<a[i] then t:=a[i]; writeln(t);阻火带 close(input); end. |
本文发布于:2024-09-23 07:26:10,感谢您对本站的认可!
本文链接:https://www.17tex.com/tex/2/166614.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
留言与评论(共有 0 条评论) |