リュックサック問題の概要とコード分析(C、OCいずれも実行可能)

リュックサック問題(Knapsack Problem)は、1つのリュックサックの荷重が最大8キロに達すると仮定し、リュックサックに荷重範囲内で得られる総価格の物品を入れたいと仮定し、果物がよくなったと仮定し、果物の番号、単価と重量は以下の通りである.
0李子4 KG NT$4500
1アップル5 KG NT$5700
2みかん2 KG NT$2250
3イチゴ1 KG NT$1100
4メロン6 KG NT$6700
解法
リュックサック問題は最適化に関する問題で、最適化問題を解くには「ダイナミックプランニング」(Dynamic programming)を使用し、空の集合から1つの要素を増やすたびにその段階の最適解を求め、すべての要素が集合に加わるまで、最後に得られるのが最適解です.
リュックサック問題を例にとると,2つのアレイvalueとitemを用い,valueは現在の最適解で得られた総価格を表し,itemは最後のリュックサックに置かれた果物を表し,負の重量1〜8のリュックサック8個があると仮定し,各リュックサックに対して最適解を求めた.
 
果物をリュックサックに徐々に入れ、この段階の最適解を求めます.
すももを入れる
リュックサックの荷重1 2 3 4 5 6 8
 value          ０       ０       ０       4500    4500    4500    4500    9000
 item            －      －        －         ０         ０        ０        ０        ０
 
りんごを入れる
リュックサックの荷重1 2 3 4 5 6 8
 value          ０        ０       ０        4500     5700   5700   5700   9000
 item            －        －       －        ０          1         1        1        ０
 
みかんを入れる
リュックサックの荷重1 2 3 4 5 6 8
 value          ０     2250     2250     4500     5700     6750     7950     9000
 item           －         2           2         ０         1           2          2         ０
 
いちごを入れる
リュックサックの荷重1 2 3 4 5 6 8
 value        1100     2250     3350     4500     5700     6800     7950     9050
 item              3       2            3          ０          1           3           2          3
 
メロンを入れる
リュックサックの荷重1 2 3 4 5 6 8
 value          1100     2250     3350     4500     5700     6800     7950     9050
 item             3          2           3          ０          1           3          2            3
 
最後の表によると、リュックサックの重さが8キロの場合、最大9050元の果物を入れることができ、最後の果物は3番、つまりイチゴで、イチゴが入っていることがわかります.バックパックは7キロ(8-1)の果物しか入れられないので、バックパックが7キロのときのベスト解を見なければなりません.最後に入れたのは2番、つまりみかんで、今バックパックにはマイナス5キロ(7-2)が残っているので、マイナス5キロのベスト解を見て、最後に入れたのは1番、つまりりんごで、このときバックパックがマイナス0キロ残っています(5-5)、果物を入れることができないので、イチゴ、オレンジ、リンゴを入れるのが最適解で、総価格は9050元です.
コードおよびコメント

#define LIMIT 8   //     
#define N 5       //     
#define MIN 1     //     

struct body {
    char name[20];
    int size;
    int price;
};

typedef struct body object;

//   
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;//         newvalue 
        if(newvalue > value[s]) {//        ，          
            value[s] = newvalue;//         
            item[s] = i;//          
        }
    }
}
printf("  \t  
");
for(i = LIMIT; i >= MIN; i = i - a[item[i]].size) {
    printf("%s\t%d
",
           a[item[i]].name, a[item[i]].price);
}
printf("  \t%d
", value[LIMIT]);