贪婪法:0-1背包问题

时间:2022-03-16 04:20:33

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

贪婪法: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、根据物品价值选择;

贪婪法:0-1背包问题

2、根据物品重量选择;

贪婪法:0-1背包问题