Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1095054
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-01-25 19:12:21

0-1背包问题描述:
有n个物品,标示为1、2、3....n,重量分别为w1、w2、....wn,价值分别为v1、v2、....vn,
有一背包,能承受的最大重量为C,问用该背包装哪些物品可以获得最大价值?

动态规划分析:
只需找出optimal substructure 就可以了。
设m(i,j)表示可选物品为1、2、3、....i,背包剩余容量为j时的最优解。
我们最终求的结果是m(n,C),n为物品件数,C为背包总容量。

递推是为:
m(i,j)=
        max( m(i-1,j), m(i-1,j-wi)+vi )   j>=wi;
        m(i-1,j)                          j
初始化条件为:
m(1,j)=
        v1         j>=w1;
        0          0<=j

伪代码大概描述为:
for j in 0 to C
    if j>=w1
        m(1,j)=v1;
    else
        m(1,j)=0;
for i in 2 to n
for j in 0 to C
if j    m(i,j)=m(i-1,j);
else
    m(i,j)=max(m(i-1,j),m(i-1,j-wi)+vi);

print m(n,C)

以上代码只是求出了背包可以装的最大价值,但没有具体给出装哪些物品来获取最大价值,
在每一步选择的时候增加标志即可记录所选择的物品。


阅读(800) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~