Chinaunix首页 | 论坛 | 博客
  • 博客访问: 103798
  • 博文数量: 35
  • 博客积分: 2386
  • 博客等级: 大尉
  • 技术积分: 380
  • 用 户 组: 普通用户
  • 注册时间: 2009-05-05 06:11
文章分类

全部博文(35)

文章存档

2011年(1)

2010年(2)

2009年(32)

分类:

2009-06-09 10:50:45

摘录自《数据结构、算法与应用——C++语言描述》

 

问题描述

对容量为C的背包进行装载,从n个物品中选取装入背包的物品,每件物品的i重量为Wi、价值为Pi。对于可行的背包进行装载,背包中物品的总重量不能超过背包的容量。最佳装载是指所装入的物品价值最高。这里Xi=1表示物品i装入背包,Xi=0表示物品i不装入背包

 

分析

    动态规划算法与分治法类似,其基本思想是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的,若用分治法解这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪婪算法有些一样,在动态规划中,可将一个问题的解决方案视为一系列决策的结果。不同的是,在贪婪算法中,每采用一次贪婪准则便做出一个不可撤回的决策,而在动态规划中,还要考察每个最优决策序列中是否包含一个最优子序列。

    最优决策序列由最优决策子序列组成。假设f (i,y)表示剩余容量为y,剩余物品为i, i+1, …, n时的最优解的值,即:

       f (n,y) = Pn, if yWn

       f (n,y) = 0,  if 0yWn

                f (i,y) = max (f (i+1,y), f (i+1, y-Wi) + Pi)           yWi

                f (i,y) = f (i+1,y)                                                    0yWi

        这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的,所以有必要将它详细解释一下:“将前i件物品放入容量为y的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为y的背包中”,价值为f[i-1][y];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为y-Wi的背包中”,此时能获得的最大价值就是f[i-1][y-Wi]再加上通过放入第i件物品获得的价值Pi。


权为整数的迭代方法

// Compute F(i,y)
// 复杂度为O(nc)
template <class T>
void Knapsack(T p[], int w[], int c, int n, T **f)
{
    for (int y = 0; y <= MAX; y++)
        f[n][y] = 0;
    for (int y = w[n]; y <= c; y++)
        f[n][y] = p[n];
    
    for (int i = n - 1; i > 1; i--) {
        for (int y = 0; y <= MAX; y++)
            f[i][y] = f[i+1][y];
        for (int y = w[i]; y <= c; y++)
            f[i][y] = max(f[i+1][y], f[i+1][y-w[i]] + p[i]);        
    }
    
    f[1][c] = f[2][c];
    if (c >= w[1])
        f[1][c] = max(f[1][c], f[2][c-w[1]] + p[1]);
}

// Find out the optimal answer
// 复杂度为O(n)
template <class T>
void Trackback(T **f, int w[], int c, int n, int x[])
{
    for (int i = 1; i < n; i++)
        if (f[i][c] == f[i+1][c])
            x[i] = 0;
        else {
            x[i] = 1;
            c -= w[i];
        }
    
    x[n] = f[n][c]?1:0;
}

 

不足

1)  要求权为整数

2)  当背包容量C很大时,执行效率变低。一般地,若C>2^n,复杂性变为Ω(n 2^n)

 

 

 

 

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