背包问题（Knapsacks Problem）
总的来说，背包问题是一种动态优化问题。
背包载重量一定，给定一组物品，没件物品有自己的价值和重量，问题要求在不超过背包载重前题下，怎样让载入的物品价值和最大？
假如有物品如下：
物品号 物品名 重量 价钱
0 李子 4 4500
1 苹果 5 5700
2 橘子 2 2250
3 草莓 1 1100
4 甜瓜 6 6700
解决问题要用到动态规划（Dynamic programming),从空集合开始，每增加一个元素就先求出该阶段的最优解，知道所有的元素加入到集合中，最后就可以得到最优解。其实是求出了在每个重量单位的最优解，是一个最优解数列。
代码中value代表目前最优解所得的总和，item表示最后一个放入背包的水果。
我们可以这样想，把问题逆过来考虑，假设最后放入的是2#，则之前背包只能放下（8-2）的重量了，后二个放入的是苹果，则之前只能放入（8-2-5）的重量了，以此类推，只考虑他的每个载重量的最优解，以每个物品为单位以此加入，得到最优解数列。
#include<stdio.h> #include<stdlib.h> #define LIMIT 8 #define N 5 #define MIN 1 struct body{ char name[20]; int size; int price; }; typedef struct body object; int main(void){ int item[LIMIT+1] ={0}; int value[LIMIT+1] = {0}; int newvalue,i,s,p; object a[] = {{"李子",4,4500}, {"苹果",5,5700}, {"橘子",2,2250}, {"草莓",1,1100}, {"甜瓜",6,6700}}; for(i = 0;i<N;i++){ for(s=a[i].size;s<=LIMIT;s++){ p=s-a[i].size; newvalue = value[p]+a[i].price; if(newvalue>value[s]){ value[s] = newvalue; item[s] = i; } } } printf("物品\t价格\n"); for(i=LIMIT;i>=MIN;i=i-a[item[i]].size){ printf("%s\t%d\n",a[item[i]].name,a[item[i]].price); } printf("合计\t%d\n",value[LIMIT]); return 0; }
