0%

【算法导论】贪心算法之背包问题

发表于 更新于
本文字数： 4.2k 阅读时长 ≈ 6 分钟

​ 在讨论贪心算法时，我们先了解贪心算法与动态规划之间的区别与联系，后面我们将发现可以用0、1背包问题和部分背包问题来比较贪心算法和动态规划的关系。

​ 我们知道，对于一个最优解问题，贪心算法不一定能够产生一个最优解。因为，如果想要采用贪心算法得到最优解需要满足两个条件：贪心选择性质、最优子结构。

  • 贪心选择性质：一个全局最优解可以通过局部最优解来得到。that is to say, 当考虑如何做选择时，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。
  • 最优子结构：全局最优解包含子问题的最优解。
  • 贪心算法和动态规划的区别：在动态规划中，每一步都要做出选择，但是这些选择都依赖于子问题的解。因此，解动态规划问题一般是自底向上，由子问题到问题。在贪心算法中，我们总是做出当前的最好选择，而这些选择都不是依赖子问题，选择后再解决选择之后出现的子问题。因此，解贪心算法问题一般是自顶向下，一个一个地做出贪心选择。

​ 从上面的描述可知，动态规划中解决问题，需要先解决子问题，因此可能用到递归（当然可以将递归化为非递归），计算复杂度要比贪心算法高。从上面的理论解释可能比较抽象，我们可以用具体的实例来说明问题。我们用经典的0、1背包问题和部分背包问题来看看动态规划和贪心算法的区别。两个问题的描述如下：

图1

用贪心选择算法来解决部分背包问题正如上面所说的思想，十分简单，在这里就不给予程序实现。我们主要讨论0、1背包问题的最优解。

​ 下面我们例子来说明为什么贪心选择算法不能解0、1背包问题：假设背包容量为$116$，序号为$1-3$的物品的重量和价格分别为：$w[3]={100, 14, 10}, p[3]={20, 18, 15}$。其平均价值为${0.2, 18/14, 1.5}$，按照贪心算法的话，选择物品顺序为：$3, 2, 1$，最终的选择为$3, 2$，其价值为$33$，但是实际的最优方案为：选择$1, 2$，其价值为$38$。

从这个例子中可以看出，在0、1背包问题中，我们在选择是否要加入一个物品时，必须将把该物品加进去的子问题和不加进去的子问题进行比较（选择依赖子问题），这种方式的问题导致了许多重叠子问题，这是动态规划的一个特点。

​ 下面我们用动态规划来解0、1背包问题：假设$f[i][j]$表示剩余物品为$i, i+1, \cdots , n$，容量为$j$时的最大价值，例如以上面的例子来说明，$f[0][10]$，表示物品为$1, 2, 3$，容量为$116$时的最大价值，$f[1][116]$，表示物品为$2, 3$，容量为$116$时的最大价值。我们目的是求$f[0][116]$，利用动态规划的思想，假设我们选择$1$号物品，则最大价值为$p[0]+f[1][116-100]$，如果不选$1$号，则最大价值为$f[1][116]$，因此选不选$1$号则需要比较两者的最大值。比较两者的最大值需要求$f[1][116]$和$f[1][116-100]$，这是重叠子问题。最终的表达式为：$f[i][j]=f[i+1][j]>f[i+1][j-w[i]]+p[i]$。这个表达式可以递归求解，当然也可以迭代求解。

具体程序实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<stdio.h>

int Bag_0or1(int *w,int *p,int *flag,int n,int i,int y);
void Bag_0or1_iteration(int *w,int *p,int c,int n,int f[][116]);
void print(int *w,int *flag,int n,int c,int f[][116]);

void main()
{
	int w[]={100,14,10};//被注释的部分是另外一个实例
	int p[]={20,18,15};
	int c=116;
	int n=2;
	//int w[]={2,2,6,5,4};
	//int p[]={6,3,5,4,6};
	//int c=10;
	//int n=4;//n为物品个数减一，是因为数组从0开始。
	int i=0;
	int f[5][116]={0};
	int flag[5]={0};//flag为1表示选择该物品
    printf("最大价值为：%d\n",Bag_0or1(w,p,flag,n,i,c));
	printf("选择的物品为（1表示选择，0表示未选择）：");
	printf("%d%d%d\n",flag[0],flag[1],flag[2]);
	 //Bag_0or1_iteration(w,p,c-1,n,f);
	 //printf("最大价值为：%d\n",f[0][c-1]);
	 //printf("选择的物品为（1表示选择，0表示未选择）：");
	 //print(w,flag,n,c-1,f);
	 //printf("\n");
}
/***************************************************\
函数功能：递归法解0/1背包问题
输入：    物品重量w、物品价格p,物品个数n、i,y表示剩余容量为y,剩余物品为i,i+1,……n
输出：    背包所能容下的最大价值
\***************************************************/
int Bag_0or1(int *w,int *p,int *flag,int n,int i,int y)//递归法
{
		if(i==n)//物品仅剩余最后一件
		{
			if(y<w[n])
			{
				flag[n]=0;
				return 0;
			}
			else
			{
				flag[n]=1;
				return p[n];
			}
		}
		if(y<w[i])//当物品i加入后大于容量的情况
		{
			flag[i]=0;
			printf("ok");
			return Bag_0or1(w,p,flag,n,i+1,y);
		}
		if(Bag_0or1(w,p,flag,n,i+1,y)>(Bag_0or1(w,p,flag,n,i+1,y-w[i])+p[i]))
		//当物品i加入后还有剩余容量的情况
		{
			flag[i]=0;
			return Bag_0or1(w,p,flag,n,i+1,y);
		}
		else
		{
			flag[i]=1;
			return Bag_0or1(w,p,flag,n,i+1,y-w[i])+p[i];
		}

}
/***************************************************\
函数功能：迭代法解0/1背包问题
输入：    物品重量w、物品价格p,物品个数n、i,y表示剩余容量为y,剩余物品为i,i+1,……n，
          f[i][j]表示剩余物品为i,i+1,……n,容量为j时的最大价值
输出：    无
\***************************************************/
void Bag_0or1_iteration(int *w,int *p,int c,int n,int f[][116])//迭代法
{
	
	for(int y=0;y<=c;y++)//初始化
		f[n][y]=0;
	for(int y=w[n];y<=c;y++)//这里有很多y值根本用不到，但是由于不能知道y的取值，所以要考虑所有y的取值
		f[n][y]=p[n];

	for(int i=n-1;i>0;i--)
	{
		for(int y=0;y<=c;y++)
			f[i][y]=f[i+1][y];
		for(int y=w[i];y<=c;y++)//选择当前物品i是否装入
		{
			if(f[i+1][y]>(f[i+1][y-w[i]]+p[i]))
				f[i][y]=f[i+1][y];//不装入
			else
				f[i][y]=f[i+1][y-w[i]]+p[i];//装入
		}
	}
	f[0][c]=f[1][c];
	if(c>=w[0])//考虑是否将第一个物品装入
	{
		if(f[0][c]>(f[1][c-w[0]]+p[0]))
			f[0][c]=f[0][c];
		else
			f[0][c]=f[1][c-w[0]]+p[0];
	}
}

/***************************************************\
函数功能：打印被选择的物品
输入：    物品重量w、是否被选择的标志flag,物品个数n、c为背包容量
          f[i][j]表示剩余物品为i,i+1,……n,容量为j时的最大价值
输出：    无
\***************************************************/
void print(int *w,int *flag,int n,int c,int f[][116])
{
	for(int i=0;i<n;i++)
	{
		if(f[i][c]==f[i+1][c])//不装入序号为i的物品的情况
			flag[i]=0;
		else
		{
			flag[i]=1;
			c=c-w[i];
		}
		flag[n]=(f[n][c])?1:0;
	}
	for(int j=0;j<=n;j++)
		printf("%d",flag[j]);

}
坚持原创技术分享，您的支持将鼓励我继续创作！