C++解决背包问题（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("%st%dn",a[item[i]].name,a[item[i]].price);
    }
 
    printf("合计t%dn",value[LIMIT]);
    return 0;
}