题目：国王和金矿问题

有一个国家发现了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

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

for i ← 0 to n - 1 do //为表格赋初值for j ← 0 to w[i] dom[i, j] ← 0;for j ← w[i] to c dom[i, j] ← v[i];for i ← 0 to n - 1 do //将价值最高的重新填入表格for j ← 0 to w[i] doif j < w[i] thenm[i,j] ← m[i-1, j];elsem[i,j] ← max{ m[i-1, j], m[i-1,j-w[i]] + v[i] }for i ← n-1 to 1 do//判断第2至n个物品是否放入背包if m[i][c] =m[i-1][c] then//第i个物品没放入背包x[i] ← 0else//第i个物品放入背包x[i] ← 1c ← c - w[i]if m[0][c] > 0//第1个物品是否放入背包x[0] ← 1//是elsex[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;}