295-0-1背包问题

蔚落 2023-01-16 06:55 77阅读 0赞

## 0-1背包问题![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center] ##

**要么装，要么不装！！！**  
**不存在装一半**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

## 我们假设X序列 ##

![在这里插入图片描述][20210424203047430.png_pic_center]  
**0代表不装，1代表装。X就是最大价值序列。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
**我们选择从x1来缩小问题的规模**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
**然后我们从x2后开始，以此类推，缩小问题的规模**

## 最优子结构性质 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]

## 我们假设c ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]

**j代表背包承受的重量，i代表放的物品。**  
**c(i,j)代表的就是最大的价值！**

## 数学递归表达式 ##

**i==n，代表放的是第n个物品，从去来看，放的一个物品。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
**我们是从头开始缩小问题规模**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]  
**表达式**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]

## 解题代码 ##

#include<iostream>
    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;
    }

**运行程序**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]

## 换种思路：正向走 ##

![在这里插入图片描述][20210424205658790.png_pic_center]  
**我们从尾部开始缩小问题的规模**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]  
**代码如下：**

#include<iostream>
    #include<vector>
    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;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 13]

## 优化 ##

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

## 递归写法 ##

#include<iostream>
    #include<vector>
    using namespace std;
    
    void Print_Vector(vector<vector<int> >& 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<vector<int> >& 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<vector<int> >& 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<vector<int> > dp(n + 1, vector<int>(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;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 16]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 17]

## 非递归写法 ##

#include<iostream>
    #include<vector>
    using namespace std;
    
    void Print_Vector(vector<vector<int> >& 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<vector<int> >& 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<vector<int> >& 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<vector<int> > dp(n + 1, vector<int>(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;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 18]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 19]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/1572cf1641ab4a338374b137295a7b52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/7843ebe1bb244b3391786e659b4a21e5.png
[20210424203047430.png_pic_center]: /images/20221022/05c595c8d87f4aa1b0865d0852748f5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/d3b05eb442a5440f9d99e444b5b2d9ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/3ac6763c2ba9424e86a0ae5cbdb6135f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221022/d56cc4b0090f4a7dbbabb25a66ad0551.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221022/00f96ce2a48a48a0adfc82b5502eb044.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221022/a1dc0bbd9243413ba8013fb68d9248b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221022/f6c0f14ea9b942adaaadfae5a24663d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221022/7e8b1023b27147cc94130c4e40c0e625.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221022/0fc8a94e05aa472e813a50c75b966a51.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221022/32c0301d8aef4fe19c33e80dcb273340.png
[20210424205658790.png_pic_center]: /images/20221022/185f54c1d124434a9317b5dd5ef720f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221022/ac111dd3e9314877960f8bac1ae885a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221022/46861d9178e747a99615466dcb07e9c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221022/cecdc278da434248858968fa300dc14d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221022/05dd349356a64fa3903ec0a15106af84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221022/60a19427635746288a004bb1f78ad6af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221022/01d625f974214137a7829a683fff25de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 17]: /images/20221022/df954f4b92394e93b1c7842abc67d40f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 18]: /images/20221022/9f5f605724cb4370baa922cad7105d6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 19]: /images/20221022/9ac21d421ae44997811fddec03982ee1.png