美文网首页动态规划
动态规划解决背包问题（0-1、完全）

动态规划解决背包问题（0-1、完全）

作者: 空白少侠 | 来源:发表于2017-04-15 15:42 被阅读152次

0-1背包问题

0~1背包（ZeroOnePack）: 有n件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的体积是volume[i]，价值是value[i]。求解将哪些物品装入背包可使价值总和最大。

0-1背包问题的特点: 每个物品只有两种状态 装 与 不装
在考虑当前第 i 个物品时，背包还剩 v 这么大的容量有可以有三个问题

  • 当前背包可以装下吗？
  • 装进此物品背包里总价值是多少？
  • 不装此物品背包里总价值是多少？

我们肯定会选择能使背包价值最大的方式解决第 i 件物品。
f[i][v]表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值

  • 放入第 i 件物品: f[i - 1][v - volume[i]] + value[i]
  • 不放入第 i 件物品: f[i-1][v]

状态方程：f[i][v]=max{f[i - 1][v - volume[i]] + value[i], f[i-1][v]}

递推方法：

#include<stdlib.h>
#include<stdio.h>
#define MAX 100
#define V 10
int value[MAX + 1]  = {4, 8, 10, 1};
int volume[MAX + 1] = {2, 3,  3, 1},n = 4;
int F[MAX + 1][MAX + 1];
int max(int x,int j){
    return x > j ? x : j;
}
int main(){
    int i,j,l,s;
    for(i = 1;i <= n;i++){
        for (j = 1; j <= V; j++) {//i 和 j 从 1 开始但是value和 volume下标从0开始所以表达式有变化
            if(j >= volume[i-1]){
                F[i][j] = max(F[i-1][j],F[i-1][j - volume[i-1]] + value[i-1]);
            }
            else F[i][j] = F[i-1][j];
            
            for(l = 1;l <= n;l++){//输出看表的变化
                for(s = 1;s <= V;s++)
                    printf("%3d",F[l][s]);
                printf("\n");
            }
            printf("\n");
        }
    }
    return 0;
}

很直观的看到二维表的维护过程

  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18  0  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22  0  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22  0
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  0  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  0  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  4  0  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  4 10  0  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  4 10 11  0  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  4 10 11 14  0  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  4 10 11 14 18  0  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  4 10 11 14 18 19  0  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  4 10 11 14 18 19 22  0  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  4 10 11 14 18 19 22 23  0

  0  4  4  4  4  4  4  4  4  4
  0  4  8  8 12 12 12 12 12 12
  0  4 10 10 14 18 18 22 22 22
  1  4 10 11 14 18 19 22 23 23

此种方法维护的是一张二维表
时间和空间复杂度均为O(N*V)
其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。
状态转移式f[v]=max{f[v],f[v-c[i]]}

#include<stdlib.h>
#include<stdio.h>
#define MAX 100
#define V 10
int value[MAX + 1]  = {4, 8, 10, 1};
int volume[MAX + 1] = {2, 3,  3, 1},n = 4;
int f[MAX];

int max(int x,int j){
    return x > j ? x : j;
}

int main(){
    int i,j,s;
    for(i = 1;i <= n;i++){
        for(j = V;j > 0;j--){
            if(j >= volume[i-1])
            f[j] = max(f[j], f[ j - volume[i-1]] + value[i-1]);
            printf("f[%2d]",j);
            for(s = 0;s < V+1 ;s++){
                printf("%3d ",f[s]);
            }
            printf("\n");
        }
        printf("\n");
        printf("\n");
    }
    return 0;
}

打印结果 很直观能看到一维表的维护过程

f[10]  0   0   0   0   0   0   0   0   0   0   4 
f[ 9]  0   0   0   0   0   0   0   0   0   4   4 
f[ 8]  0   0   0   0   0   0   0   0   4   4   4 
f[ 7]  0   0   0   0   0   0   0   4   4   4   4 
f[ 6]  0   0   0   0   0   0   4   4   4   4   4 
f[ 5]  0   0   0   0   0   4   4   4   4   4   4 
f[ 4]  0   0   0   0   4   4   4   4   4   4   4 
f[ 3]  0   0   0   4   4   4   4   4   4   4   4 
f[ 2]  0   0   4   4   4   4   4   4   4   4   4 
f[ 1]  0   0   4   4   4   4   4   4   4   4   4 


f[10]  0   0   4   4   4   4   4   4   4   4  12 
f[ 9]  0   0   4   4   4   4   4   4   4  12  12 
f[ 8]  0   0   4   4   4   4   4   4  12  12  12 
f[ 7]  0   0   4   4   4   4   4  12  12  12  12 
f[ 6]  0   0   4   4   4   4  12  12  12  12  12 
f[ 5]  0   0   4   4   4  12  12  12  12  12  12 
f[ 4]  0   0   4   4   8  12  12  12  12  12  12 
f[ 3]  0   0   4   8   8  12  12  12  12  12  12 
f[ 2]  0   0   4   8   8  12  12  12  12  12  12 
f[ 1]  0   0   4   8   8  12  12  12  12  12  12 


f[10]  0   0   4   8   8  12  12  12  12  12  22 
f[ 9]  0   0   4   8   8  12  12  12  12  22  22 
f[ 8]  0   0   4   8   8  12  12  12  22  22  22 
f[ 7]  0   0   4   8   8  12  12  18  22  22  22 
f[ 6]  0   0   4   8   8  12  18  18  22  22  22 
f[ 5]  0   0   4   8   8  14  18  18  22  22  22 
f[ 4]  0   0   4   8  10  14  18  18  22  22  22 
f[ 3]  0   0   4  10  10  14  18  18  22  22  22 
f[ 2]  0   0   4  10  10  14  18  18  22  22  22 
f[ 1]  0   0   4  10  10  14  18  18  22  22  22 


f[10]  0   0   4  10  10  14  18  18  22  22  23 
f[ 9]  0   0   4  10  10  14  18  18  22  23  23 
f[ 8]  0   0   4  10  10  14  18  18  22  23  23 
f[ 7]  0   0   4  10  10  14  18  19  22  23  23 
f[ 6]  0   0   4  10  10  14  18  19  22  23  23 
f[ 5]  0   0   4  10  10  14  18  19  22  23  23 
f[ 4]  0   0   4  10  11  14  18  19  22  23  23 
f[ 3]  0   0   4  10  11  14  18  19  22  23  23 
f[ 2]  0   0   4  10  11  14  18  19  22  23  23 
f[ 1]  0   1   4  10  11  14  18  19  22  23  23

从打印数量上来看 确实优化许多

递归方法

#include<stdlib.h>
#include<stdio.h>
#define MAX 100
#define V 10
int value[MAX + 1] = {4, 8, 10, 5}, volume[MAX + 1] = {2, 3, 2, 1},n = 4;
int dp[MAX + 1][MAX + 1];//记忆数组
int max(int x,int j){
    return x > j ? x : j;
}
int f(int i,int j){
    int totlaValue = 0;
    if(dp[i][j] != -1)//是否计算过了
        return dp[i][j];
    if(i >= n)//没东西了
        return 0;
    if(volume[i] > j){//无法装下
    dp[i + 1][j] = f(i + 1,j);//记下
    } else {
        totlaValue = max(f(i + 1, j - volume[i] ) + value[i],f(i+1, j));//取最大者
    }
    dp[i][j] = totlaValue;//记下
    return totlaValue;
}
int main(){
    memset(dp,-1,sizeof(dp));
    printf("%d" ,f(0,V));
    return 0;
}

完全背包(CompletePack): 有n物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是volume[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值
f[i][v] = max{f[i - 1][v - k*c[i]] + k * w[i]|0 <= k*c[i] <= v}

既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c[i]件，于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
状态转移方程：
f[v]=max{f[v],f[v-cost]+weight}

#include<stdlib.h>
#include<stdio.h>
#define MAX 100
#define V 10
int value[MAX + 1]  = {4, 8, 10, 1};
int volume[MAX + 1] = {2, 3,  3, 1},n = 4;
int f[V];

int max(int x,int j){
    return x > j ? x : j;
}

int main(){
        int i,j,l,s;
    f[0] = 0;
    for(i = 0;i <= n;i++){
        for(j = 0;j <= V;j++){
            if(j >= volume[i]){
            
            f[j] = max(f[j], f[j - volume[i]] + value[i]);
            }
            printf("f[%2d]",j);
            
            for(s = 0;s < V+1 ;s++){
                printf("%3d ",f[s]);
            }
            printf("\n");
        }
         printf("\n");
    }
    
    return 0;
}


f[ 0]  0   0   0   0   0   0   0   0   0   0   0 
f[ 1]  0   0   0   0   0   0   0   0   0   0   0 
f[ 2]  0   0   4   0   0   0   0   0   0   0   0 
f[ 3]  0   0   4   4   0   0   0   0   0   0   0 
f[ 4]  0   0   4   4   8   0   0   0   0   0   0 
f[ 5]  0   0   4   4   8   8   0   0   0   0   0 
f[ 6]  0   0   4   4   8   8  12   0   0   0   0 
f[ 7]  0   0   4   4   8   8  12  12   0   0   0 
f[ 8]  0   0   4   4   8   8  12  12  16   0   0 
f[ 9]  0   0   4   4   8   8  12  12  16  16   0 
f[10]  0   0   4   4   8   8  12  12  16  16  20 

f[ 0]  0   0   4   4   8   8  12  12  16  16  20 
f[ 1]  0   0   4   4   8   8  12  12  16  16  20 
f[ 2]  0   0   4   4   8   8  12  12  16  16  20 
f[ 3]  0   0   4   8   8   8  12  12  16  16  20 
f[ 4]  0   0   4   8   8   8  12  12  16  16  20 
f[ 5]  0   0   4   8   8  12  12  12  16  16  20 
f[ 6]  0   0   4   8   8  12  16  12  16  16  20 
f[ 7]  0   0   4   8   8  12  16  16  16  16  20 
f[ 8]  0   0   4   8   8  12  16  16  20  16  20 
f[ 9]  0   0   4   8   8  12  16  16  20  24  20 
f[10]  0   0   4   8   8  12  16  16  20  24  24 

f[ 0]  0   0   4   8   8  12  16  16  20  24  24 
f[ 1]  0   0   4   8   8  12  16  16  20  24  24 
f[ 2]  0   0   4   8   8  12  16  16  20  24  24 
f[ 3]  0   0   4  10   8  12  16  16  20  24  24 
f[ 4]  0   0   4  10  10  12  16  16  20  24  24 
f[ 5]  0   0   4  10  10  14  16  16  20  24  24 
f[ 6]  0   0   4  10  10  14  20  16  20  24  24 
f[ 7]  0   0   4  10  10  14  20  20  20  24  24 
f[ 8]  0   0   4  10  10  14  20  20  24  24  24 
f[ 9]  0   0   4  10  10  14  20  20  24  30  24 
f[10]  0   0   4  10  10  14  20  20  24  30  30 

f[ 0]  0   0   4  10  10  14  20  20  24  30  30 
f[ 1]  0   1   4  10  10  14  20  20  24  30  30 
f[ 2]  0   1   4  10  10  14  20  20  24  30  30 
f[ 3]  0   1   4  10  10  14  20  20  24  30  30 
f[ 4]  0   1   4  10  11  14  20  20  24  30  30 
f[ 5]  0   1   4  10  11  14  20  20  24  30  30 
f[ 6]  0   1   4  10  11  14  20  20  24  30  30 
f[ 7]  0   1   4  10  11  14  20  21  24  30  30 
f[ 8]  0   1   4  10  11  14  20  21  24  30  30 
f[ 9]  0   1   4  10  11  14  20  21  24  30  30 
f[10]  0   1   4  10  11  14  20  21  24  30  31 

f[ 0]  0   1   4  10  11  14  20  21  24  30  31 
f[ 1]  0   1   4  10  11  14  20  21  24  30  31 
f[ 2]  0   1   4  10  11  14  20  21  24  30  31 
f[ 3]  0   1   4  10  11  14  20  21  24  30  31 
f[ 4]  0   1   4  10  11  14  20  21  24  30  31 
f[ 5]  0   1   4  10  11  14  20  21  24  30  31 
f[ 6]  0   1   4  10  11  14  20  21  24  30  31 
f[ 7]  0   1   4  10  11  14  20  21  24  30  31 
f[ 8]  0   1   4  10  11  14  20  21  24  30  31 
f[ 9]  0   1   4  10  11  14  20  21  24  30  31 
f[10]  0   1   4  10  11  14  20  21  24  30  31

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

相关文章

  • 算法-动态规划-背包问题

    背包问题是基础的动态规划问题，包含了0-1背包，完全背包，多重背包等。 0-1背包 存在容量为 的背包 ， 件体...

  • 背包问题

    背包问题属于典型的动态规划问题。这里我们将详细介绍0-1背包，完全背包和多重背包问题 一、 0-1背包 有N件物品...

  • 动态规划-0-1背包问题

    动态规划-0-1背包问题 动态规划（dynamic programming）是解决多阶段决策问题常用的最优化理论，...

  • 动态规划

    0-1背包问题 自己实现的0-1背包问题的动态规划解法，先贴上吧，动态规划原理解释有空再写。

  • 初识动态规划

    0-1 背包问题 备忘录 动态规划-二维数组 动态规划-一维数组 0-1 背包问题升级版 回溯算法 动态规划-二维...

  • Algorithm进阶计划 -- 动态规划（下）

    经典动态规划背包问题最长子序列问题 1. 背包问题 1.1 0-1 背包问题 0-1 背包问题，描述如下： 上面...

  • 数据结构与算法笔记day23：动态规划

    1初识动态规划 这节课的内容不涉及动态规划的理论，而是通过两个例子：0-1背包问题、0-1背包问题升级...

  • LeetCode 动态规划专题 5：0-1 背包问题

    这一节我们介绍使用动态规划解决的一个非常经典的问题：0-1 背包问题。 0-1 背包问题描述 问题描述： 有一个背...

  • 动态规划解决背包问题（0-1、完全）

    0-1背包问题 0~1背包（ZeroOnePack）: 有n件物品和一个容量为V的背包。（每种物品均只有一件）第i...

  • lintcode-k数和

    动态规划（确定0-1背包、完全背包、多重背包）0-1背包：每个元素要么出现，要么不出现，逆序遍历，数组定义为：前i...

网友评论

    本文标题：动态规划解决背包问题（0-1、完全）

    本文链接：https://www.haomeiwen.com/subject/mcfnwttx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    动态规划

    关于我们|服务条款|联系我们|动态规划解决背包问题（0-1、完全）|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！