动态规划方法求解0-1背包问题

摘录自《数据结构、算法与应用——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 y≥Wn

       f (n,y) = 0,  if 0≤y≤Wn

和

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

                f (i,y) = f (i+1,y)                                                    0≤y≤Wi

        这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的，所以有必要将它详细解释一下：“将前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)