贪婪法：0-1背包问题

参考书目：《算法的乐趣》作者: 王晓华

 

贪婪法，又叫贪心算法，是寻找最优解问题的常用方法。

基本设计思想的三个步骤：

1）建立对问题的数学建模

2）将问题分解成子问题，同时定义子问题的最优解结构

3）利用贪心原则确定子问题的局部最优解，根据最优解模型，将子问题的局部最优解堆叠出全局最优解

优点：简单高效，省去了为找最优解可能需要的穷举操作，可得到与最优解接近的近似最优解，常作为其他算法的辅助算法使用。

缺点：由于不进行回溯操作，大多数情况下，会错过最优解或者说得不到真正的最优解。

以0-1背包问题作为贪婪法的例子。

0-1背包问题：有N件物品和一件承重为C的背包（或体积），每件物品的重量为Wi，价值为Pi，求解将哪几件物品装入背包可使这些物品在重量总和不超过C的情况下价值总和最大。

背包问题（knapsack problem）是此类组合优化的NP完全问题的总称。类似的比如：货箱装载问题、货船载物问题等。

常见的贪婪策略有三种：

1、根据物品价值选择；

2、根据物品重量选择；

3、定义一个价值密度（Pi/Wi）的概念

下面的代码只涉及第一第二种，在codebook下编译的时候一直有错，找了半天没发现；后来放在VS2015下编译，能够正确编译并且得到正确的答案。很疑惑，代码应该还是有点小问题的也不够严谨。

先把代码存下来，如果有人发现了问题希望能告诉我，谢谢各位！也欢迎提出不足之处！

/*
2018-3-17
贪心算法实现0-1背包问题
copyright @GCN
*/

#include <stdio.h>
#include <stdlib.h>

//策略一：根据物体的价值进行选择
int Pick_P(int p[], int s[], int n)
{
	int i, temp = 0, max = 0;
	for (i = 0; i<n; i++)
	{
		if (s[i] == 0 && p[i] >= max)
		{
			max = p[i];
			temp = i;
		}
		//printf("\n%d,max=%d\n",i,max);
	}
	return temp;
}
//策略二：根据物体的重量进行选择
int Pick_W(int p[], int s[], int n)
{
	int i, temp = 0, min = 99999;
	for (i = 0; i<n; i++)
	{
		if (s[i] == 0 && p[i] <= min)
		{
			min = p[i];
			temp = i;
		}
		//printf("\n%d,min=%d\n",i,min);
	}
	return temp;
}
int main()
{
	int i, m, xz = 0;
	int j = 0, n = 7, ntc = 0, ntp = 0;
	int c = 150;//背包容量
	int w[] = { 35,30,60,50,40,10,25 };//物体重量
	int p[] = { 10,40,30,50,35,40,30 };//物体价值
	int s[] = { 0,0,0,0,0,0,0 };//状态
	int t[] = { 0 }, tnum = 0;
	printf("背包的最大容量:150\n");
	printf("物品的个数:7\n");
	printf("物体的重量分别为:\n");
	for (i = 0; i<n; i++)
	{
		printf("%d\t", w[i]);
	}
	printf("\n");
	printf("物体的价值分别为:\n");
	for (i = 0; i<n; i++)
	{
		printf("%d\t", p[i]);
	}
	printf("\n");
	printf("物体的初始状态分别为:\n");
	for (i = 0; i<n; i++)
	{
		printf("s[%d]=%d\t", i, s[i]);
	}
	printf("\n");
	printf("以何种策略进行选择(0/1)：");
	scanf_s("%d", &xz);

	for (m = 0; m<n&&ntc <= c; m++)
	{
		switch (xz)
		{
		case 0:
			j = Pick_P(p, s, n);
			break;
		case 1:
			j = Pick_W(w, s, n);
			break;
		}
		if ((ntc + w[j]) <= c)
		{
			ntc += w[j];
			ntp += p[j];
			s[j] = 1;
			t[m] = ntc;
		}
		else if ((ntc + w[j])>c)
		{
			s[j] = 2;
		}
		if ((m != 0 && t[m]>t[m - 1]) || (m == 0 && t[m] <= c))
		{
			tnum += 1;
			printf("\n第%d次:选中第%d件物品,重%d,价值为%d\n", (m + 1), (j + 1), w[j], p[j]);
			printf("此时背包中承载的物品重量%d\n", t[m]);
		}
		else
			break;
	}
	printf("\n共选择%d个物品，总价值为%d\n", tnum, ntp);

	return 0;
}

附上实验结果

1、根据物品价值选择；

2、根据物品重量选择；