【C语言/算法之 01 背包】完全背包

古城微笑少年丶 2022-08-05 04:19 169阅读 0赞

**\[题目\]**

有 N  种物品和一个容量为 V 的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

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

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件⋯⋯等很多种。如果仍然按照解01背包时的思路，令f\[i\]\[v\]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

**f\[i\]\[v\] = max\{f\[i-1\]\[v-k\*c\[i\]\] + k\*w\[i\] | 0 <= k\*c\[i\] <= v \}**

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

输出结果如下：

0 10 10 20 20 30 30 40 40 50 50 60 60 70 70 80 80 90 90  
1 10 11 20 21 30 31 40 41 50 51 60 61 70 71 80 81 90 91  
1 10 11 20 21 30 31 40 41 50 51 60 61 70 71 80 81 90 91  
1 10 11 20 21 30 31 40 41 50 51 60 61 70 71 80 81 90 91  
1 10 11 20 21 30 31 40 41 50 51 60 61 70 71 80 81 90 91  
The final result = 91

这跟01背包问题一样有O(VN)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态f\[i\]\[v\]的时间是O(v/c\[i\])，总的复杂度可以认为是O(V\*Σ(V/c\[i\]))，是比较大的。

将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。

**f\[v\] = max\{f\[v-k\*c\[i\]\] + k\*w\[i\] | 0 <= k\*c\[i\] <= v \}**

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