动态规划---背包问题分析-白红宇

动态规划---背包问题分析

阅读量：6720 次

发布时间：2019-06-25

本文共 7550 字，大约阅读时间需要 25 分钟。

0/1背包

　　问题描述

有N件物品和一个容量为V的背包，第i件物品的体积为c[i]，价值为w[i]。求将哪些物品放进背包可以使物品价值总和最大（有两种情况：不要求填满背包和填满背包）。

每件商品只有一件，且只能选择放或者不放入背包。

　　解决方案

使用动态规划求解，定义一个递归式opt[i][v]表示前i个物品，在背包容量大小为v的情况下，最大的价值。

opt[i][v] = max(opt[i-1][v], opt[i-1][v-c[i]] + w[i])

其中opt[i-1][v]表示第i件物品不装入背包中的总价值，而opt[i-1][v-c[i]]+w[i]表示第i件物品装入背包中的总价值。

通过初始化不同来区别两种情况，第一种情况，不要求填满背包，则：

for i <-0 to V    f[i] <- 0

第二种情况，要求填满背包，则

f[0] <- 0for i <-1 to V    f[i] <- -65536

可以理解为，在要求填满背包的情况下，我们只选择上一步的最大价值不小于0的情况，也就是说，在上一步已经满足了填满当时容量的条件，表示从0到V的容量里都填满了物品；而不像不要求填满背包那样，只关心最大价值，而不保证每个容量单位里面都有物品。

由于每个物品只有1件，所以采用从V向下递减，以此保证每个物品在每次循环过程中只被计算了1遍。

花费的时间复杂度为O(V*T)。

　　伪代码

PACKAGE(w, c, V)#ifdef CANEMPTY    for i <- 0 to V        f[i] <- 0#else    f[0] <- 0    for i <- 1 to V        f[i] <- -65536#endif    for i <- 0 to n        for v <- V downto c[i]            f[v] = max(f[v-c[i]] + w[i], f[v])    return f[V]

　　代码

#include 
     
      using namespace std;const int V = 100;const int T = 8;int f[V+1];int w[T] = {
   3, 4, 6, 2, 3, 5, 1, 4};int c[T] = {
   15, 25, 20, 10, 30, 20, 5, 15};int package(){#ifdef EMPTY    f[0] = 0;    for(int i = 1; i <= V; i++)        f[i] = -65536;#else    for(int i = 0; i <= V; i++)        f[i] = 0;#endif        for(int i = 0; i < T; i++)    {        for(int v = V; v > c[i]; v--)        {            f[v] = f[v - c[i]] + w[i] > f[v] ? f[v - c[i]] + w[i]: f[v];        }    }    return f[V];}int main(int argc, char *argv[]){        cout<<"The Max Value is "<
      
       <

完全背包问题

　　问题描述

有N种物品（数量不限）和一个容量为V的背包，第i件物品的体积为c[i]，价值为w[i]。求将哪些物品放进背包可以使物品价值总和最大（有两种情况：不要求填满背包和填满背包）。

　　解决方案

动态规划法，推导出递归公式：

f[j] = max(f[j], f[j – w[i]] + v[i])

其中f[j]表示容量为j时的最大价值，f[j-w[i]]+v[i]表示f[j]中包含了第i个物品。

由于每个物品有n件，所以采用从0向上递加，以此保证每个物品在每次循环过程中只被计算了1遍。

同样，两种情况也只是初始化的值不同，同0-1背包问题。

　　伪代码

COMPLETE_PACKAGE(w, c, V, N)#ifdef CANEMPTY    for i <- 0 to V        f[i] <- 0#else    f[0] <- 0    for i <- 1 to V        f[i] <- -65536#endif    for i <- 0 to N        for j <- c[i] to V                    f[j] = max(f[j], f[j - c[i]] + w[i])    return f[V]

　　代码

#include 
     
      using namespace std;const int V = 100;const int T = 8;int f[V+1];int w[T] = { 3,  4,  6,  2,  3,  5, 1,  4};int c[T] = {
   15, 25, 20, 10, 30, 20, 5, 15};int complete_package(){#ifdef EMPTY    for(int i = 0; i <= V; i++)        f[i] = 0;#else    f[0] = 0;     for(int i = 1; i <= V; i++)         f[i] = -65536;#endif        for(int i = 0; i < T; i++)        for(int v = c[i]; v <= V; v++)            f[v] = (f[v - c[i]] + w[i]) > f[v] ? (f[v - c[i]] + w[i]):f[v];    return f[V];}int main(int argc, char *argv[]){    cout<<"The Max Value is "<
      
       <

多重背包问题

　　问题描述

有N种物品（不定个数）和一个容量为V的背包，第i件物品的体积为c[i]，价值为w[i]，数量为n[i]。求将哪些物品放进背包可以使物品价值总和最大（有两种情况：不要求填满背包和填满背包）。

　　解决方案

可以转换为0-1背包问题。转换方式为，将第i件物品合并成若干种物品，n[i] – 2^k + 1 > 0即k < log(n[i] – 1)，取k的最大值，以2^0,2^1…2^(k-1),n[i]-2^k+1为系数，每件合并后的物品的体积和价值都乘以相应的系数组成不同的物品。如：

第i件物品有13件，那么k的最大值为3，系数为1,2,4,6，组成的新物品的体积分别为c[i], 2*c[i],4*c[i]和6*c[i]，价值为w[i],2*w[i],4*w[i]和6*w[i]。这样，对所有的物品都进行类似的合并，组成一个新的物品集合，然后利用0-1背包来解决剩下的问题。

组成新物品系数选定的理由：可以看出，新的系数可以保证在任意组合后，都能获取到0~n[i]个物品的数值，如：n[i]=13,那么我想用其中的10个这样的物品，可以由合并后的系数4和6组成。

　　伪代码

Merge_Goods(w, c, n, N)    j <- 0    for i <- 0 to N        p <- 1        while p < n[i] + 1            nw[j] <- p * w[i]            nc[j] <- p * c[i]            p <- p * 2            j <- j + 1        if p / 2 < n[i]            nw[j] <- (n[i] - p / 2) * w[i]            nc[j] <- (n[i] - p / 2) * c[i]    nN = j    return nN and nw and ncPACKAGE(nw, nc, V, nN)#ifdef CANEMPTY    for i <- 0 to V        f[i] <- 0#else        f[0] <- 0    for i <- 1 to V        f[i] <- -65536#endif    for i <- 0 to nN        for v <- V downto nc[i]            f[v] <- max(f[v-nc[i]] + nw[i], f[v])    return f[V]

　　代码

#include 
     
      #define MAXNUM 1000#define EMPTYint nc[MAXNUM];int nw[MAXNUM];int merge_goods(int c[], int w[], int n[], int N){    int j = 0;    for(int i = 0 ; i < N; i++)    {        int p = 1;        while(p < n[i] + 1)        {            nc[j] = p * c[i];            nw[j] = p * w[i];            p = p * 2;            j++;        }        if(p/2 < n[i])        {            nc[j] = (n[i] - p / 2) * c[i];            nw[j] = (n[i] - p / 2) * w[i];            j++;        }    }    return j;}int multi_package(int c[], int w[], int n[], int V, int N){    int nN = merge_goods(c, w, n, N);    int f[V+1];#ifdef EMPTY    for(int i = 0 ; i <= V; i++)        f[i] = 0;#else    f[0] = 0;    for(int i = 1; i <= V; i++)        f[i] = -65536;#endif    for(int i = 0; i < nN; i++)    {        for(int j = V; j >= nc[i]; j--)        {            f[j] = (f[j - nc[i]] + nw[i] > f[j]) ? (f[j - nc[i]] + nw[i]) : f[j];        }    }    return f[V];}int main(int argc, char *argv[]){    int T = 8;    int V = 300;    int w[] = { 3,  4,  6,  2,  3,  5, 1,  4};    int c[] = {
   15, 25, 20, 10, 30, 20, 5, 15};        int n[] = { 7, 13,  8,  4, 15, 12, 9, 11};    cout<<"Max Value is "<

二维背包问题

问题描述

一维、二维或者多维是针对于代价来说的，以前讨论的三种背包问题都是在代价为一维的条件下，获取最大价值的，该问题的代价是二维的，即可以理解为背包有体积和承重两种代价限制，分别为V和U，获取在这两种代价的上限内所能得到的最大价值。

解决方案

如果理解了之前的背包问题，该问题的解决办法也就一目了然了，简单的说，就是将之前的f[v]变为f[v][u]，将以前的一次循环，变为了两次循环，其它没有理论上的不同了。

如果是0-1背包问题，u和v倒序循环；如果是完全背包问题，则u和v正序进行循环。

f[i][u][v] = max(f[i-1][u][v] , w[i] + f[i-1][u-a[i]][v-b[i]])

伪代码（只写出0-1背包，且不要求某个代价为上限值的情况）

Two_Package(w, a, b, U, V, N)    for i <- 0 to U        for j <- 0 to V            f[i][j] <- 0    for i <- 0 to N        for u <- U downto a[i]            for v <- V downto b[i]                f[v][u] = max(f[u-a[i]][v-b[i]]+w[i], f[u][v])    return f[u][v]

　　代码

#include 
     
      int two_package(int w[], int a[], int b[], int U, int V, int N){    int f[U+1][V+1];    for(int i = 0; i <= U; i++)        for(int j = 0; j <= V; j++)            f[i][j] = 0;        for(int i = 0; i < N; i++)    {        for(int u = U; u >= a[i]; u--)        {            for(int v = V; v >= b[i]; v--)                f[u][v] = (f[u - a[i]][v - b[i]] + w[i] > f[u][v]) ? (f[u - a[i]][v - b[i]] + w[i]):f[u][v];        }    }    return f[U][V];}int main(int argc, char *argv[]){    const int V = 120;    const int U = 140;    const int T = 8;        int w[T] = { 3,  4,  6,  2,  3,  5,  1,  4};    int a[T] = {
   15, 25, 20, 10, 30, 20,  5, 15};    int b[T] = {
   10, 30, 15, 10, 20, 20, 10, 20};    cout<<"Max Value is "<

分组背包问题

　　问题描述

有N种物品和一个容量为V的背包，第i件物品的体积为c[i]，价值为w[i]。现将所有物品分成若干组，每组中的物品相互冲突，即在选择时，每组中只能最多选择一件物品，求将哪些物品放进背包可以使物品价值总和最大（有两种情况：不要求填满背包和填满背包）。

　　解决方案

可以将k个分组看成k个物品，当做0-1背包问题处理，然后再对每个分组中的单个物品进行选择。

f[k][v] = max(f[k][v], f[k][v-c[k][i]]+w[i])

　　伪代码

Group_Package(w, c, K, V, N)    for i <- 0 to V        f[i] <- 0        for k <- 0 to K        for v <- V downto 0            for i <- 0 to N                if v > c[k][i]                    f[v] = max(f[v], f[v - c[k][i]] + w[k][i])    return f[V]

　　代码

#include 
     
      const int K = 3;const int N = 4;int w[K][N] = {    {
    3, 4, 6, 2},    {
    3, 5, 1, 4},    {
    6, 2, 3, 5}};int c[K][N] = {    {
    15, 25, 20, 10},    {
    20, 15, 30, 20},    {
    30, 30, 20, 5}};int group_package(int V){    int f[V + 1];    for(int i = 0; i <= V; i++)        f[i] = 0;        for(int k = 0; k < K; k++)    {        for(int v = V; v >= 0; v--)        {            for(int i = 0; i < N; i++)            {                if(c[k][i] <= v)                    f[v] = (f[v - c[k][i]] + w[k][i] > f[v]) ? (f[v - c[k][i]] + w[k][i]) : f[v];            }        }    }    return f[V];}int main(int argc, char *argv[]){    int V = 60;    cout<<"Max Value is "<
      
       <