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

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]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

最后编辑于：2017.12.06 01:02:28

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 213,711评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,079评论 3赞 387
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,194评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,089评论 1赞 286
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,197评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,306评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,338评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,119评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,541评论 1赞 306
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,846评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,014评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,694评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,322评论 3赞 318
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,026评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,257评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,863评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,895评论 2赞 351

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

0-1背包问题

推荐阅读更多精彩内容