動態(tài)規(guī)劃解決背包問題（0-1暖眼、完全）

0-1背包問題

0~1背包（ZeroOnePack）: 有n件物品和一個容量為V的背包。（每種物品均只有一件）第i件物品的體積是volume[i]躏嚎，價值是value[i]蜜自。求解將哪些物品裝入背包可使價值總和最大。

0-1背包問題的特點: 每個物品只有兩種狀態(tài) 裝與不裝
在考慮當(dāng)前第 i 個物品時紧索，背包還剩 v 這么大的容量有可以有三個問題

當(dāng)前背包可以裝下嗎袁辈？
裝進此物品背包里總價值是多少菜谣？
不裝此物品背包里總價值是多少珠漂？

我們肯定會選擇能使背包價值最大的方式解決第 i 件物品。
f[i][v]表示前 i 件物品恰放入一個容量為 v 的背包可以獲得的最大價值

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

狀態(tài)方程：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下標(biāo)從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

此種方法維護的是一張二維表
時間和空間復(fù)雜度均為O(N*V)
其中時間復(fù)雜度基本已經(jīng)不能再優(yōu)化了尾膊，但空間復(fù)雜度卻可以優(yōu)化到O(V)媳危。

先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1..N冈敛，每次算出來二維數(shù)組f[i][0..V]的所有值待笑。那么，如果只用一個數(shù)組f[0..V]抓谴，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢暮蹂？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環(huán)中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢癌压？事實上仰泻，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態(tài)f[i-1][v-c[i]]的值滩届。
狀態(tài)轉(zhuǎn)移式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;
}

打印結(jié)果很直觀能看到一維表的維護過程

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

從打印數(shù)量上來看確實優(yōu)化許多

遞歸方法

#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];//記憶數(shù)組
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的背包的最大權(quán)值
f[i][v] = max{f[i - 1][v - k*c[i]] + k * w[i]|0 <= k*c[i] <= v}

既然01背包問題是最基本的背包問題辈讶，那么我們可以考慮把完全背包問題轉(zhuǎn)化為01背包問題來解。最簡單的想法是娄猫，考慮到第i種物品最多選V/c[i]件贱除，于是可以把第i種物品轉(zhuǎn)化為V/c[i]件費用及價值均不變的物品，然后求解這個01背包問題稚新。這樣完全沒有改進基本思路的時間復(fù)雜度勘伺，但這畢竟給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。
狀態(tài)轉(zhuǎn)移方程：
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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市钦无，隨后出現(xiàn)的幾起案子逗栽，更是在濱河造成了極大的恐慌，老刑警劉巖失暂，帶你破解...
沈念sama閱讀 217,907評論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件彼宠，死亡現(xiàn)場離奇詭異，居然都是意外死亡弟塞，警方通過查閱死者的電腦和手機凭峡，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,987評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來决记，“玉大人摧冀，你說我怎么就攤上這事∠倒” “怎么了索昂？”我有些...
開封第一講書人閱讀 164,298評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長扩借。經(jīng)常有香客問我椒惨，道長，這世上最難降的妖魔是什么往枷？我笑而不...
開封第一講書人閱讀 58,586評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任框产，我火速辦了婚禮，結(jié)果婚禮上错洁，老公的妹妹穿的比我還像新娘秉宿。我一直安慰自己，他們只是感情好屯碴，可當(dāng)我...
茶點故事閱讀 67,633評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布描睦。她就那樣靜靜地躺著，像睡著了一般导而。火紅的嫁衣襯著肌膚如雪忱叭。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,488評論 1贊 302
城市分裂傳說
那天今艺，我揣著相機與錄音韵丑，去河邊找鬼。笑死虚缎，一個胖子當(dāng)著我的面吹牛撵彻，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播，決...
沈念sama閱讀 40,275評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼陌僵，長吁一口氣：“原來是場噩夢啊……” “哼轴合！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起碗短，我...
開封第一講書人閱讀 39,176評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤受葛，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后偎谁，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體总滩，經(jīng)...
沈念sama閱讀 45,619評論 1贊 314
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,819評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年搭盾，在試婚紗的時候發(fā)現(xiàn)自己被綠了咳秉。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片婉支。...
茶點故事閱讀 39,932評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡鸯隅，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出向挖，到底是詐尸還是另有隱情蝌以，我是刑警寧澤，帶...
沈念sama閱讀 35,655評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布何之，位于F島的核電站跟畅，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏溶推。R本人自食惡果不足惜徊件，卻給世界環(huán)境...
茶點故事閱讀 41,265評論 3贊 329
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望蒜危。院中可真熱鬧虱痕，春花似錦、人聲如沸辐赞。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,871評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽响委。三九已至新思，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間赘风，已是汗流浹背夹囚。一陣腳步聲響...
開封第一講書人閱讀 32,994評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留邀窃，地道東北人荸哟。一個月前我還...
沈念sama閱讀 48,095評論 3贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長得像，于是被迫代替她去往敵國和親敲茄。傳聞我的和親對象是個殘疾皇子位谋，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 44,884評論 2贊 354

動態(tài)規(guī)劃解決背包問題（0-1屯远、完全）

動態(tài)規(guī)劃解決背包問題（0-1暖眼、完全）

0-1背包問題

推薦閱讀更多精彩內(nèi)容