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

0-1背包问题

要么装，要么不装！！！

不存在装一半

我们假设X序列

0代表不装，1代表装。X就是最大价值序列。 我们选择从x1来缩小问题的规模 然后我们从x2后开始，以此类推，缩小问题的规模

最优子结构性质

我们假设c

j代表背包承受的重量，i代表放的物品。

c(i,j)代表的就是最大的价值！

数学递归表达式

i==n，代表放的是第n个物品，从去来看，放的一个物品。

我们是从头开始缩小问题规模 表达式

解题代码

#include
   
    using namespace std;int Knapsack(int W[], int V[], int i, int n, int j){   	if (i == n)	{   		return j >= W[n] ? V[n] : 0;	}	else if (j < W[i])//不用装了	{   		return Knapsack(W, V, i + 1, n, j);	}	else	{   		int max1 = Knapsack(W, V, i + 1, n, j);		int max2 = Knapsack(W, V, i + 1, n, j - W[i]) + V[i];		return max1 > max2 ? max1 : max2;	}}int main(){   	const int n = 5;	const int c = 10;	int W[n + 1] = {    0,2,2,6,5,4 };//0下标不放数据 ，重量 	int V[n + 1] = {    0,6,3,5,4,6 };//0下标不放数据 ，最大价值 	int maxv = Knapsack(W, V, 1, n, c);	cout << maxv << endl;}
   

运行程序

换种思路：正向走

我们从尾部开始缩小问题的规模 代码如下：

#include
   
    #include
    
     using namespace std;int Knapsack(int W[], int V[], int i, int j){   	if (i == 1)	{   		return j >= W[1] ? V[1] : 0;	}	else if (j < W[i])	{   		return Knapsack(W, V, i - 1, j);	}	else	{   		int max1 = Knapsack(W, V, i - 1, j);		int max2 = Knapsack(W, V, i - 1, j - W[i]) + V[i];		return max1 > max2 ? max1 : max2;	}}int main(){   	const int n = 5;	const int c = 10;	int W[n + 1] = {    0,2,2,6,5,4 };//0下标不放数据 ，重量 	int V[n + 1] = {    0,6,3,5,4,6 };//0下标不放数据 ，最大价值 	int maxv = Knapsack(W, V, n, c);	cout << maxv << endl;}
    
   

优化

5个物品，10重量

当物品是0个，不管背包的容量多大，价值为0，当背包的容量为0，不管多少个物品，都是0。 当我们放这5个物品，当我们的背包容量=10的时候，我们的最大价值=15。 到底哪些物品我们存放了，哪些物品我们没有存放？ 从第5个物品开始看，15和14不相等，所以第5个物品我们放！它的重量是6。 10-4=6。容量=6的时候，9和9相等，物品4，物品3没放，物品2放。

递归写法

#include
   
    #include
    
     using namespace std;void Print_Vector(vector
     
      
        >& c, int m, int n){   	for (int i = 0; i <= m; ++i)	{   		for (int j = 0; j <= n; ++j)		{   			printf("%4d", c[i][j]);		}		printf("\n");	}	printf("\n");}int Knapsack(int W[], int V[], int i, int j,	vector
       
        
          >& dp){ if (i == 1) { dp[i][j]= j >= W[1] ? V[1] : 0; } else if (dp[i][j] > 0) { return dp[i][j]; } else if (j < W[i]) { dp[i][j] = Knapsack(W, V, i - 1, j, dp); } else { int max1 = Knapsack(W, V, i - 1, j, dp); int max2 = Knapsack(W, V, i - 1, j - W[i], dp) + V[i]; dp[i][j]= max1 > max2 ? max1 : max2; } return dp[i][j];}void BackPack(int W[], const vector
         
          
            >& dp, int n, int c, bool X[]){ for (int i = n; i > 0; --i) { if (dp[i][c] != dp[i - 1][c]) { X[i] = true;//放进去 c -= W[i];//减去i的重量 } }}int main(){ const int n = 5; const int c = 10; int W[n + 1] = { 0,2,2,6,5,4 }; int V[n + 1] = { 0,6,3,5,4,6 }; bool X[n + 1] = { }; vector
           
            
              > dp(n + 1, vector
             
              (c + 1, 0)); //n+1代表物品的个数，c+1代表重量 int maxv = Knapsack(W, V, n, c, dp); cout << maxv << endl; Print_Vector(dp, n, c); BackPack(W, dp, n, c, X); return 0;}
             
            
           
          
         
        
       
      
     
    
   

非递归写法

#include
   
    #include
    
     using namespace std;void Print_Vector(vector
     
      
        >& c, int m, int n){       for (int i = 0; i <= m; ++i)    {           for (int j = 0; j <= n; ++j)        {               printf("%4d", c[i][j]);        }        printf("\n");    }    printf("\n");}int Knapsack(int W[], int V[], int n, int c,    vector
       
        
          >& dp){ for (int j = 1; j <= c; ++j) { if (j >= W[1]) { dp[1][j] = V[1]; } else { dp[1][j] = 0; } } for (int i = 2; i <= n; ++i) { for (int j = 1; j <= c; ++j) { if (j < W[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]); } } } return dp[n][c];}void BackPack(int W[], const vector
         
          
            >& dp, int n, int c, bool X[]){ for (int i = n; i > 0; --i) { if (dp[i][c] != dp[i - 1][c]) { X[i] = true;//放进去 c -= W[i];//减去i的重量 } }}int main(){ const int n = 5; const int c = 10; int W[n + 1] = { 0,2,2,6,5,4 }; int V[n + 1] = { 0,6,3,5,4,6 }; bool X[n + 1] = { }; vector
           
            
              > dp(n + 1, vector
             
              (c + 1, 0)); //n+1代表物品的个数，c+1代表重量 int maxv = Knapsack(W, V, n, c, dp); cout << maxv << endl; Print_Vector(dp, n, c); BackPack(W, dp, n, c, X); return 0;}
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://axyiz.baihongyu.com/