主题:装箱问题 ++分
Benix
[专家分:720] 发布于 2005-11-12 08:09:00
谁能教教我怎样用动态规划解装箱问题?? 具体思路是什么?
回复列表 (共15个回复)
11 楼
interegg [专家分:80] 发布于 2006-09-04 19:23:00
能给我具体解释一下 :
for i:=1 to n do
for k:=v downto volume[i] do
h[k]:=h[k] or h[k-volume[i]];
这段吗?
谢谢
13 楼
qiuzhi2008 [专家分:0] 发布于 2006-09-09 18:47:00
program zhuangxiang;
var
v,n,i,j,min,s:integer;
w:array[1..30] of integer; {存放物品体积}
a:array[0..30] of integer; {对应存放物品是否装箱}
begin
readln(v,n);
for i:=1 to n do read(w[i]);
for i:=0 to n do a[i]:=0;
min:=v; {最小值初始为V}
while a[0]=0 do {循环判断每一种情况}
begin
j:=n;
while a[j]=1 do dec(j); {逢1进位}
a[j]:=1; {不进位则本位加1}
for i:=j+1 to n do a[i]:=0; {低位清0}
s:=0;
for i:=1 to n do s:=s+a[i]*w[i]; {求装箱和}
if (v-s>=0) and (v-s<min) then min:=v-s; {验证最小剩余空间}
end;
writeln(min);
end.
14 楼
waglongjuanfeng [专家分:90] 发布于 2006-10-05 03:13:00
1使用贪心法
2.此题应该用不到动态规划,如果可以,请指教
15 楼
循甲天书 [专家分:100] 发布于 2006-10-09 14:10:00
此题简单得很,直接用动态
我来回复