[数据结构与算法]【算法/C语言】01背包问题（动态规划DP）

题目：国王和金矿问题

有一个国家发现了max_n座金矿，参与挖矿工人的总数是max_people人。每座金矿的黄金储量不同为一维数组gold[]，需要参与挖掘的工人数也不同为一维数组peopleNeed[]。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

功能：

(1) 要求max_n、max_people、gold和ppeopleNeed均为可输入的；

(2) 编写DP函数，求解答案F；

(3) 编写main主函数，完成输入，调用DP函数和显示答案结果。

样例输入1：

5

92 22 87 46 90

100

77 22 29 50 99

样例输出1：

133

3 4

思路：

max_n看做物品的数量n ；

max_people看做背包容量c ；

gold看做物品的价值v；

peopleNeed看做物品的重量w?。

根据01背包问题求解即可。

伪码：

Function knapsack(n, c, *w, *v)

输入：物品数量n，背包容量c，物品的重量*w，物品的价值*v

输出：放入背包的物品和背包中的最大价值

1. for i ← 0 to n - 1 do //为表格赋初值
2. ???for j ← 0 to w[i] do
3. ??????m[i, j] ← 0;
4. ???for j ← w[i] to c do
5. ??????m[i, j] ← v[i];
6. for i ← 0 to n - 1 do //将价值最高的重新填入表格
7. ???for j ← 0 to w[i] do
8. ??????if j < w[i] then
9. ?????????m[i,j] ← m[i-1, j];
10. ?????else
11. ????????m[i,j] ← max{ m[i-1, j], m[i-1,j-w[i]] + v[i] }
12. for i ← n-1 to 1 do//判断第2至n个物品是否放入背包
13. ???if m[i][c] =m[i-1][c] then//第i个物品没放入背包
14. ??????x[i] ← 0
15. ???else//第i个物品放入背包
16. ??????x[i] ← 1
17. ??????c ← c - w[i]
18. if m[0][c] > 0//第1个物品是否放入背包
19. ???x[0] ← 1//是
20. else
21. ???x[0] ← 0//否

时间复杂度：O(nc)

具体：

用二维数组创建一个表格，先给表格赋初值：

j < w[ i ] 时，m[ i ][ j ] = 0 ；?

w[ i ] < j < c 时，m[ i ][ j ] = v[ i ] 。

再由第 i 个物品的放或者不放重填表格：

j < w[ i ] 时（不放），m[ i ][ j ] = m[ i - 1 ][ j ]?；

否则（放），取?m[ i - 1 ][ j ]（不放）和?m[ i - 1 ][ j - w[ i ] ] + v[ i ]（放）的最大值

?m[ i ][ j ] = max( m[ i - 1 ][ j ], ( m[ i - 1 ][ j - w[ i ] ] + v[ i ] ) )?。

此时，背包的最大价值为 m[ n ][ c ] 。

接着求放了哪几个物品：

?? ?for(i = n - 1; i > 0; i--){
?? ??? ?if(m[i][c] == m[i-1][c]){
?? ??? ??? ?x[i] = 0;
?? ??? ?}else{
?? ??? ??? ?x[i] = 1;
?? ??? ??? ?c = c - w[i];
?? ??? ?}
?? ?}?? ??? ?
?? ?if(m[0][c] > 0){
?? ??? ?x[0] = 1;
?? ?}else{
?? ??? ?x[0] = 0;
?? ?}

实现：?

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

int max(int a, int b){
	if(a > b){
		return a;
	}else{
		return b;
	}
} 

void knapsack(int n, int c, int *w, int *v){
	int i,j;
	int m[n][c+1];
	
	int *x;
	x = (int*)malloc(n * sizeof(int));
	
	//先给表格赋初值 
	for(i = 0; i < n; i++){
		for(j = 0; j < w[i]; j++){
			m[i][j] = 0; 
		}
		for(j = w[i]; j < c + 1; j++){
			m[i][j] = v[i];
		}
	}
	/*
	for(i = 0;i<n;i++){
		for(j=0;j<c+1;j++){
			printf("%d\t",m[i][j]); 
		}
		printf("\n");
	}
	printf("\n");
	*/
	for (i = 1; i < n; i++) {
		for (j = 0; j < c + 1; j++) {
			if (j < w[i]){
				m[i][j] = m[i - 1][j];
			}
			else{
				m[i][j] = max(m[i - 1][j], (m[i - 1][j - w[i]] + v[i]));
			}
		}
	}
	/*
	for(i = 0;i<n;i++){
		for(j=0;j<c+1;j++){
			printf("%d\t",m[i][j]);
		}
		printf("\n");
	}
	*/
	printf("能够得到黄金的价值为：%d\n",m[n-1][c]);	

	//判断放入背包的物品 
	for(i = n - 1; i > 0; i--){
		if(m[i][c] == m[i-1][c]){
			x[i] = 0;
		}else{
			x[i] = 1;
			c = c - w[i];
		}
	}		
	if(m[0][c] > 0){
		x[0] = 1;
	}else{
		x[0] = 0;
	}
	
	printf("应该挖取第");
	for(i = 0; i < n; i++){
		if(x[i] == 1){
			printf("%d,",i+1);
		}
	}
	printf("座金山");
}

int main(){
	int max_n,max_people;
	int *gold,*peopleNeed; 
	int i,j;
	
	//物品的数量n 
	printf("金矿（max_n）的数量：");
	scanf("%d",&max_n);
	
	//物品的价值v 
	gold = (int*)malloc(max_n * sizeof(int));
	for(i = 0; i < max_n; i++){
		printf("第%d座金矿的黄金储量：",(i+1));
		scanf("%d",&gold[i]);
	}
	
	//背包容量c 
	printf("参与挖矿工人（max_people）的数量：");
	scanf("%d",&max_people);
	
	//物品的重量w 
	peopleNeed = (int*)malloc(max_people * sizeof(int));
	for(i = 0; i < max_n; i++){
		printf("挖掘第%d座金矿需要参与挖掘的工人数：",(i+1));
		scanf("%d",&peopleNeed[i]);
	} 
	
	knapsack(max_n,max_people,peopleNeed,gold);
	
	return 0;
	
}