[1] ナップサック問題を全探索で再帰的に解く.
[1.1]
標準出力から
最大重量W
品物の個数n(1≦n≦64)
1個目の品物の価値v0 1個目の品物の重量w0
2個目の品物の価値v1 2個目の品物の重量w1
...
n個目の品物の価値vn-1 n個目の品物の重量wn-1
をこの順で受け取り重量の合計がWを超えない範囲で価値の合計が最大になるような品物の組み合わせを求め, その組み合わせに含まれる品物の価値と重量の合計を表示する.
knapsack関数はstruct item型の配列への参照A配列の先頭の添字b, 配列の長さl, 最大重量Wを受け取り, bからl-1番目の品物についてナップサック問題を解き, 答えとなる合計価値vと合計重量wを返すというものである. この関数は, 計算を行った後, vをret_priceが指す先の変数に保存し, wを返り値をして返す.
double knapsack(struct item *A, int b, int l, double W, int *ret_price)
{
}
[1.2]
#include <stdio.h>
struct item {
int price; //品物の価値
double weight; //品物の重量
};
double knapsack(struct item *A, int b, int l, double W, int *ret_price);
int main()
{
struct item item[64];
double W;
int n, i, v;
scanf("%lf", &W);
scanf("%d",&n);
for(i = 0; i < n; i++) {
scanf("%d %lf",&item[i].price, &item[i].weight);
}
knapsack(&item[0], 0, n, W, &v);
printf("%d\n", v);
printf("%f\n", knapsack(&item[0], 0, n, W, &v));
return 0;
}
double knapsack(struct item *A, int b, int l, double W, int *ret_price)
{
int v, v2, w, w2;
if(b == l) {
return 0;
}
if(W < A[b].weight) {
v = knapsack(A, b+1, l, W, ret_price);
w = knapsack(A, b+1, l, W, ret_price);
*ret_price = v;
return w;
}
else {
w = knapsack(A, b+1, l, W, ret_price);
w2 = A[b].weight + knapsack(A, b+1, l, W-A[b].weight, ret_price);
v = knapsack(A, b+1, l, W, ret_price);
v2 = A[b].price + knapsack(A, b+1, l, W-A[b].weight, ret_price);
}
if(v > v2) {
*ret_price = v;
}
else {
*ret_price = v2;
}
return w > w2 ? w : w2;
}
例えば, 実行時以下のように入力を行うと
200
3
20 100
15 70
12 50
35 //最大価値v
170 //最大重量w
となるべきところが
200
3
20 100
15 70
12 50
120
170
のようになってしまいます.
[1.4] プログラムの間違っている箇所を教えていただきたいです.
どうぞよろしくお願いいたします. 長文失礼しました.