发布时间 : 星期六 文章贪心算法详解更新完毕开始阅读8e53bfca5a8102d277a22f2b
for e:=1 to n-1 do if d<>a[e]then begin
a[e+1]:=a[e+1]+a[e]-d; a[e]:=d; f:=f+1; end; write(f); end; end. 金银岛
描述
某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类, 每种金属重量不同，分别为n1, n2, ... , ns，同时每个种类的金属总的价值也不同，分别为v1,v2, ..., vs。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。
输入
第1行是测试数据的组数k，后面跟着k组输入。
每组测试数据占3行，第1行是一个正整数w (1 <= w <= 10000)，表示口袋承重上限。第2行是一个正整数s (1 <= s <=100)，表示金属种类。第3行有2s个正整数，分别为n1, v1, n2, v2, ... , ns, vs分别为第一种，第二种，...，第s种金属的总重量和总价值(1 <= ni <= 10000, 1 <= vi <= 10000)。
输出
k行，每行输出对应一个输入。输出应精确到小数点后2位。
样例输入 2 50 4 10 100 50 30 7 34 87 100 10000 5 1 43 43 323 35 45 43 54 87 43 样例输出
171.93 508.00 贪心题目，先算出每种金属单价d， 按照d进行排序， 然后贪心地拣前面几个，直到背包满。 var
a,b:array[0..100] of longint; p:array[0..100] of real; n,i,j,k,s,m,g:longint; tot:real;
procedure sort(l,r: longint); var
i,j,y:longint; x,tt:real; begin i:=l; j:=r;
x:=p[(l+r) div 2]; repeat
while p[i] inc(i); dec(j); begin tt:=p[i]; p[i]:=p[j]; p[j]:=tt; y:=a[i]; a[i]:=a[j]; a[j]:=y; y:=b[i]; b[i]:=b[j]; b[j]:=y; inc(i); j:=j-1; while x end; until i>j; if l sort(l,j); sort(i,r); if i readln(k); for g:=1 to k do begin readln(m); readln(s); for i:=1 to s do begin read(a[i],b[i]); p[i]:=b[i]/a[i]; end; tot:=0; sort(1,s); i:=s; while (i>0)and(m>0) do if m>=a[i] then begin dec(m,a[i]); tot:=tot+b[i]; dec(i); end else begin tot:=tot+m*p[i]; m:=0; end; writeln(tot:0:2); end; end. 装箱问题 ? ? ? ? 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB 描述 一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。 输入 输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用空格隔开，分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。 输出 除了输入的最后一行6个0以外，输入文件里每一行对应着输出文件的一行，每一行输出一个整数代表对应的订单所需的最小包裹数。 样例输入 0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0 样例输出 2 1 解题思路 这个问题描述得比较清楚，在这里只解释一下输入输出样例：共两组有效输入，第一组表示有4 个3X3的产品和1个6X6的产品，此时4个3X3的产品占用一个箱子，另外1个6X6的产品占用一个箱子，所以箱子数是2；第二组表示有7个1X1的产品，5个2X2的产品和1个3X3的产品，可以把它们统统放在一个箱子中，所以输出是1。 分析6个型号的产品占用箱子的具体情况如下：6X6的产品每个会占用一个完整的箱子，并且没有空余的空间；5X5的产品每个占用一个新的箱子，并且留下11个可以盛放1X1的产品的空余空间；4X4的产品每个占用一个新箱子，并且留下5个可以盛放2X2的产品的空余空间；3X3的产品比较复杂，首先3X3的产品不能放在原来盛放5X5或者4X4的箱子中，那么必须为3X3的产品另开新的箱子，新开的箱子数目等于3X3的产品的数目除以4向上取整；同时需要讨论为3X3的产品新开箱子时，剩余的空间可以盛放多少2X2和1X1的产品(这里如果空间可以盛放2X2的产品，就将它记入2X2的空余空间，等到2X2的产品全部装完，如果还有2X2的空间剩余，再将它们转换成1X1的剩余空间)。分情况讨论为3X3的产品打开的新箱子额中剩余的空位，共为4种情况：第一种，3X3的产品的数目正好是4