这是一类经典的算法问题。
问题可以描述为： 给定一组物品 x(1, n), 每个具有重量 w(1, n) 和价值 v(1, n), 如何从这组物品里选择一个子集合，使得这个子集合的元素在满足总重量 w 小于或等于给定的重量W的条件下，总价值 V 最大。
通用的算法是使用递归来求解。
V(i, w) = max(V(i -1, w), V(i -1, w- w(i))+v(i))
其中， V(i,w)为 i个物品，重量为 w时候的总价值；w(i), v(i),为第 i个物品的重量和价值。
假定编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6。从下到上，可以按照上面的递归算法填出下面的一张表：
| name | weight | value | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| a | 2 | 6 | 0 | 6 | 6 | 9 | 9 | 12 | 12 | 15 | 15 | 15 |
| b | 2 | 3 | 0 | 3 | 3 | 6 | 6 | 9 | 9 | 9 | 10 | 11 |
| c | 6 | 5 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 10 | 11 |
| d | 5 | 4 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 10 | 10 |
| e | 4 | 6 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
实现代码如下：
#include <stdio.h>
#define MAX_WEIGHT 20
#define MAX_COUNT 10
int value_map[MAX_COUNT + 1][MAX_WEIGHT];
int weight[MAX_COUNT + 1];
int value[MAX_COUNT + 1];
int result[MAX_COUNT + 1];
void fill_value_map(int count, int total_weight)
{
int j;
//first, fill the map for the last
for(j = 1; j <= MAX_WEIGHT; j++)
{
if(weight[count] > j)
{
value_map[count][j] = 0;
}
else
{
value_map[count][j] = value[count];
}
}
int i;
for( i = count - 1; i >= 1; i--)
{
for(j = 1; j < MAX_WEIGHT; j++)
{
if(weight[i] > j)
{
value_map[i][j] = value_map[i + 1][j];
}
else
{
int new_value = value_map[i+1][j] > value_map[i + 1][j - weight[i]] + value[i] ?
value_map[i + 1][j] : value_map[i + 1][j - weight[i]] + value[i];
value_map[i][j] = new_value;
}
}
}
}
void make_result(int count, int total_weight)
{
int j = total_weight;
int i;
for(i = 1; i < count; i++)
{
if(value_map[i][j] == value_map[i + 1][j])
{
result[i] = 0;
}
else
{
result[i] = 1;
j = j - weight[i];
}
}
result[i] = value_map[i][j] != 0 ? 1: 0;
}
int main(void)
{
FILE *fp = freopen("input.txt", "r", stdin);
if(fp == NULL)
{
printf("open file failed\n");
return -1;
}
int count = 0, total_weight = 0;
scanf("%d %d", &count, &total_weight);
int i;
for(i = 1; i <= count; i++)
{
scanf("%d", &weight[i]);
}
for(i = 1; i <= count; i++)
{
scanf("%d", &value[i]);
}
fill_value_map(count, total_weight);
int j;
for(i = 1; i <= count; i++)
{
for(j = 1; j <= total_weight; j++)
{
printf("%2d ", value_map[i][j]);
}
printf("\n");
}
make_result(count, total_weight);
printf("following are kept: \n");
for(i = 1; i <= count; i++)
{
if(result[i] != 0)
{
printf("%d ", i);
}
}
printf("\n");
fclose(fp);
return 0;
}
测试数据文件内容如下：
5 10 2 2 6 5 4 6 3 5 4 6运行结果如下：
$ ./test 0 6 6 9 9 12 12 15 15 15 0 3 3 6 6 9 9 9 10 11 0 0 0 6 6 6 6 6 10 11 0 0 0 6 6 6 6 6 10 10 0 0 0 6 6 6 6 6 6 6 following are kept: 1 2 5算法打印出来的结果我们手动填的是一致的。
参考：