c语言0-1背包问题

给定n种物品和1个背包，物品i的重量是wi，其价值为vi，背包的容量为C。要求选择装入背包的物品，使得装入背包中物品的总价值最大。

Input

每组测试数据包含3行，第1行为n和c，表示有n(0<=n<=400)个物品且背包容量为c (c<=1500)，第二行为这n个物品的重量wi(1<=wi<=1000)，第三行为这n个物品的价值vi。背包容量和物品重量都为整数。

Output

输出装入背包的最大总价值，每个答案一行。

Sample Input
5 10
2 2 6 5 4
6 3 5 4 6
Sample Output
15
代码:

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

#define MAXN 410

typedef struct{
	int wi;
	int vi;
}Goods;

Goods goods[MAXN];

//算法思路:贪心算法,每次都向背包里面装入价值最大的物品,如果装入超过容量c
int cmp(const void *a, const void *b)
{
	return (*(Goods*)a).vi - (*(Goods*)b).vi;
}
int main()
{
	int n, c, i,sum = 0, total = 0;
	scanf("%d %d", &n, &c);
	for(i = 0; i < n; i++)
	{
		scanf("%d", &goods[i].wi);
	}
	for(i = 0; i < n; i++)
	{
		scanf("%d", &goods[i].vi);
	}
	qsort(goods, n, sizeof(Goods),cmp);
	for(i = n - 1; i >= 0; i--)
	{
		sum += goods[i].wi;
		if(sum <= c)
		{
			total += goods[i].vi;
		}else
		{
			sum -= goods[i].wi;
		}
	}
	printf("%d\n", total);
	return 0;
}