切换到宽版
  • 13992阅读
  • 14回复

多重背包问题 [复制链接]

上一主题 下一主题
离线rocket323
 
只看楼主 正序阅读 0 发表于: 2006-07-12
有谁可以讲讲背包问题,拜托拜托~~~~~~~~
离线wangyicheng
只看该作者 14 发表于: 2007-11-16
离线fchqq
只看该作者 13 发表于: 2007-11-13
完全背包问题
For i:=1 to n do
for j:=1 to w do
begin
  f[i,j]:=f[i-1,j];  {不取当前物品i}
  for k:=1 to j/v do
  if (j>=k*v) and (f[I,j]<=f[I,j-v]+a){保证放得下第i个物品,则j-v>0==>j>v==>j>=(v到j的所有数据)}
    then f[I,j]:=f[I,j-v]+a
  end;
end;

01背包问题
For i:=1 to n do
for j:=0 to w do
begin
  f[I,j]:=f[i-1,j];  {不取当前物品i}
  if (j>=v) and (f[i-1,j-v]+a>f[I,j])
    then f[I,j]:= f[i-1,j-v]+a>f[I,j]
end;
离线percy_yu
只看该作者 12 发表于: 2007-11-13
不会啊
离线dujiangtao
只看该作者 11 发表于: 2007-11-10
 
离线dujiangtao
只看该作者 10 发表于: 2007-11-10
     
离线swj05652
只看该作者 9 发表于: 2006-11-17
其实是转自starforever的
离线archimedes

只看该作者 8 发表于: 2006-11-15
引用第5楼swj056522006-08-24 14:50发表的:
多重背包问题一般用迭代搜索。 用动规的话内存不够的。一般出这种题都会存在很好的剪枝。
以USACO 4.1.2 Fence Rails (fence8)为例:
我们用迭代搜索(DFSID)来解决。
.......

大牛~
离线q422158622
只看该作者 7 发表于: 2006-11-14
不懂~~~~~~~请问2楼,什么是不可分割的背包问题,什么是可分割的背包问题???
离线nanzheng
只看该作者 6 发表于: 2006-09-21
用动规做不行吗?
快速回复
限100 字节
 
上一个 下一个