ナップサック問題について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ATAT13621
記事: 2
登録日時: 1年前

ナップサック問題について

#1

投稿記事 by ATAT13621 » 1年前

初投稿です. C言語で次のような問題が課されたのですが, 正しい結果が出力されません. 色々調べ, 試行錯誤しながらやったのですがどうしてもうまくいきません. このプログラムの修正すべき箇所をご教授いただければ幸いです。

[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;
}
 [1.3] コンパイルは通るのですが, 正しい結果を表示することが出来ません.
例えば, 実行時以下のように入力を行うと
200
3
20 100
15 70
12 50
35  //最大価値v
170 //最大重量w
となるべきところが
200
3
20 100
15 70
12 50
120
170
のようになってしまいます.

 [1.4] プログラムの間違っている箇所を教えていただきたいです.

どうぞよろしくお願いいたします. 長文失礼しました.

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: ナップサック問題について

#2

投稿記事 by みけCAT » 1年前

・knapsack関数の返り値 (重量) をv (価値) 系の変数に代入している
・再帰呼び出しにより ret_price が指す先に格納された値を無視している
・重量と価値を独立に比較し、小さくない方を採用している
というのがおかしいですね。

・再帰呼び出しする際、 ret_price にポインタを渡す用の新しい領域 (変数) を用意し、渡すようにする
・格納された値 (価値) を比較し、小さくない方が得られた方に対応する返り値 (重量) を採用するようにする
というようにすると改善するでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

ATAT13621
記事: 2
登録日時: 1年前

Re: ナップサック問題について

#3

投稿記事 by ATAT13621 » 1年前

返信ありがとうございます!
重量と価値を独立に比較していたのがおかしいという点は理解できたのですが, 再帰呼び出しのret_priceが指す先に格納された値を無視しているというのが具体的にどういうことなのか理解できませんでした. また, 価値を比較したあと, 大きい方の重量を算出するためにはどのようにすればよいかも分からず行き詰ってます.

お手数をおかけしますが, よろしければ回答お願いします.

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: ナップサック問題について

#4

投稿記事 by みけCAT » 1年前

ATAT13621 さんが書きました:
1年前
再帰呼び出しのret_priceが指す先に格納された値を無視しているというのが具体的にどういうことなのか理解できませんでした.
ret_priceが指す先に格納された値を読み出さず、次の再帰呼び出しや間接演算子を用いた代入により上書きしてしまっている、ということです。
ATAT13621 さんが書きました:
1年前
また, 価値を比較したあと, 大きい方の重量を算出するためにはどのようにすればよいかも分からず行き詰ってます.
大きい方の価値が得られた再帰呼び出しの戻り値を、「大きい方の重量」として採用すれば良いです。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

返信

“C言語何でも質問掲示板” へ戻る