回 帖 发 新 帖 刷新版面

主题:装箱问题 ++分

谁能教教我怎样用动态规划解装箱问题?? 具体思路是什么?

回复列表 (共15个回复)

11 楼

能给我具体解释一下 :
for i:=1 to n do 
   for k:=v downto volume[i] do
     h[k]:=h[k] or h[k-volume[i]];
     
这段吗?
谢谢

12 楼

用贪心就是了

13 楼


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 楼

1使用贪心法
2.此题应该用不到动态规划,如果可以,请指教

15 楼

此题简单得很,直接用动态

我来回复

您尚未登录,请登录后再回复。点此登录或注册