【C语言/算法之 01 背包】基础版

一时失言乱红尘 2022-08-05 04:17 164阅读 0赞

设有一个背包可以放入的物品重量为V，现有n件物品，重量分别是 c1,c2,c3,…cn，价值分别为 w1,w2,w3,…wn。

问能否从这n件物品中选择若干件放入背包中，使得放入的物品的价值和最大？

**\[基本思路\]：**

01 背包问题 0 表示不放入，1 表示放入。

用子问题定义状态：即

**f\[i\]\[v\]表示前i件物品恰放入一个容量为v的背包可以获取得到的最大价值。**

可以得到以下状态转移方程。

**f\[i\]\[v\] = max \{f\[i-1\]\[v\],f\[i-1\]\[v-c\[i\]\] + w\[i\]\} ;**

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f\[i-1\]\[v\]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c\[i\]的背包中”，此时能获得的最大价值就是f\[i-1\]\[v-c\[i\]\]再加上通过放入第i件物品获得的价值w\[i\]。

#include <stdio.h>
    #include <string.h>
    
    #define max(a,b) ((a>b)?a:b)
    
    int main()
    {
    	int i,j;
    	/**
    	 * 最大重量 V = 20
    	 * 物体总共个数 N = 5
    	 */
    	int V = 20, N = 5;
    	/**
    	 * 每个物体的重量
    	 */
    	int Weight[6] = {0, 1, 3, 5, 7, 9};
    	/**
    	 * 每个物体的价值
    	 */
    	int Value[6] =  {0, 10, 2, 5, 4, 3};
    	/**
    	 * 辅助数组
    	 */
    	int f[6][21];
    
    	memset(f,0,sizeof(f));
    
    	for (i = 1; i <= N; i++)
    	{
    		for (j = 1; j <= V; j++)
    		{
    			/**
    			 * j-Weight[i] == 0 表示该物体的重量刚好等于最大允许重量
    			 */
    			if (j-Weight[i] >= 0)
    			{
    				f[i][j] = max(f[i-1][j],f[i-1][j-Weight[i]] + Value[i]);
    			}
    			else
    			{
    				f[i][j] = f[i-1][j];
    			}
    
    			printf("%-5d",f[i][j]);
    		}
    
    		printf("\n");
    	}
    
    	printf("The final result = %d",f[5][20]);
    
    	return 0;
    }

输出结果如下：

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10  
10 10 10 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12  
10 10 10 12 12 15 15 15 17 17 17 17 17 17 17 17 17 17 17 17  
10 10 10 12 12 15 15 15 17 17 17 17 19 19 19 21 21 21 21 21  
10 10 10 12 12 15 15 15 17 17 17 17 19 19 19 21 21 21 21 21  
The final result = 21

Question:如何将2维数组 f转换成为1维数组 ??

**f\[i\]\[v\] = max \{f\[i-1\]\[v\],f\[i-1\]\[v-c\[i\]\] + w\[i\]\} ;**

根据公式可以知道，f\[i\]\[v\] 只和上一行\[1,v\] 之间的数相关，于是我们简化二维数组变成一维数组存储。而必须优先计算f\[v\]，因为从前到后操作会破快之前上一行保留下来的数据，造成错误。

代码如下：

#include <stdio.h>
    #include <string.h>
    
    #define max(a,b) ((a>b)?a:b)
    
    int main()
    {
    	int i,j;
    	/**
    	 * 最大重量 V = 20
    	 * 物体总共个数 N = 5
    	 */
    	int V = 20, N = 5;
    	/**
    	 * 每个物体的重量
    	 */
    	int Weight[6] = {0, 1, 3, 5, 7, 9};
    	/**
    	 * 每个物体的价值
    	 */
    	int Value[6] =  {0, 10, 2, 5, 4, 3};
    	/**
    	 * 辅助数组
    	 */
    	//	int f[6][21];
    	int f[21];
    
    	memset(f,0,sizeof(f));
    
    	for (i = 1; i <= N; i++)
    	{
    		for (j = V; j >= 1; j--)
    		{
    			/**
    			 * j-Weight[i] == 0 表示该物体的重量刚好等于最大允许重量
    			 */
    			if (j-Weight[i] >= 0)
    			{
    				f[j] = max (f[j],f[j-Weight[i]]+Value[i]);
    			}
    
    			printf("%-5d",f[j]);
    		}
    
    		printf("\n");
    	}
    
    	printf("The final result = %d",f[20]);
    
    	return 0;
    }