c语言0-1背包问题

Dev|il

给定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 410typedef struct{int wi;int vi;}Goods;Goods goods[MAXN];//算法思路:贪心算法,每次都向背包里面装入价值最大的物品,如果装入超过容量cint 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;}