ナップザック問題

[epsilon]

ナップザック問題を解きたいです。しかし例えば

k=13
n=3
w[0]=10
w[1]=16
w[2]=2

という入力に対して

最大値--->0
組合せ--->

と返ってきてしまいます。恐らく配列a[d]にうまく0,1を入れることができていないのだと思います。助けて下さい。よろしくお願いします。

OS Windows7
コンパイラ gcc

コード:

#include<stdio.h>
#define MAX (500)

int i,k,n,w[MAX],max=0,o[MAX];
void bi(int d);

int main(void)
{
  printf("\nナップザックの最大容量kを教えて下さい.--->");
  scanf("%d",&k);
  printf("%d\n\n",k);
  
  printf("用意された品物の個数nを教えて下さい.--->");
  scanf("%d",&n);
  printf("%d\n\n",n);

  printf("%d個の品物について,重さweightを教えて下さい.\n",n);
  for(i=0;i<n;++i){scanf("%d",&w[i]);}
  for(i=0;i<n-1;++i){printf("%d,",w[i]);}
  printf("%d\n\n",w[n-1]);

  if (n<=0) printf("nは自然数にしてください.\n");

  else bi(0);
  printf("\n");
  printf("最大値--->%d\n",max);
  printf("組合せ--->\n");
  for(i=0;i<n;++i){
  if(o[i]==1) printf("w[%d]",i);}
  printf("\n");
}
 
void bi(int d)
{
  int i,total=0,a[MAX];
  if(d==n){
    for(i=0;i<n;++i){
      if(a[i]==1){
	total+=w[i];
	  }
    }
    if(total<=k && total>max){
      max=total;
      for(i=0;i<n;++i){
	o[i]=a[i];
      }
    }
  }
  
 
  else{
    a[d]=0;
    bi(d+1);

    a[d]=1;
    bi(d+1);
  }
}

[かずま]

36行目の ,a[MAX] を 5行目に移動する。

[box]

なぜ、くだんの解答のようにしなければならないか、というと、

コード:

void bi(int d)
{
  int i,total=0,a[MAX];

a[MAX]がbi()内のローカルな変数であるため、
bi()を実行する『たびに、毎回、ゴミで』初期化しているからです。

そういう意図はないですよね？

[かずま]

a[MAX]がbi()内のローカルな変数であるため、
bi()を実行する『たびに、毎回、ゴミで』初期化しているからです。

その説明は間違っています。
a[MAX] が bi() 内の自動変数であるため、bi() が呼び出されるたびに
領域が確保され、初期化が行われないため、ゴミが入っているからです、
というのが正しい説明だと思います。

コード:

int i, total = 0; static int a[MAX];

こうすると、a[MAX] は、bi() 内のローカル変数ですが、
静的変数であって、自動変数ではないため、
最初はすべてゼロで初期化され、その後も設定された値を保持しますから
グローバル変数にしなくても、目的を達成できます。

[epsilon]

ご回答ありがとうございます。つまり以下のようなことが起きているのでしょうか？

k=13
n=3
w[0]=10
w[1]=16
w[2]=2

を読み込んだ後、関数biに入り

a[0]=0
a[1]=0
a[2]=0

となる。 このとき、total==0であるから

if(total<=k && total>max)

を満たさないため、maxは更新されない。
この後、本来ならば、配列a[]の中身をクリアしなければいけないが、クリアされていない。←ココがおかしい。
よって最大値が0と表示されてしまう。

この認識で正しいですか？

[みけCAT]

違います。a[0],a[1],a[2]はそれぞれ不定の値になります。
それが0なのか、334なのか、57885161なのか、それとも全く別の値なのかは、
実行して割り当てられたメモリの中身を見るまでわかりません。
ただし、その値がたまたま1である可能性は(たまたま他の特定の値である可能性と同様に)かなり低いので、
ほとんどの場合totalは0のままになるでしょう。

[epsilon]

どうして不定になるのですか？

bi関数の中で

else
a[d]=0

を、d==nまで繰り返すから

まずa[]には0が入ると思うのですが。。。

馬鹿ですいません。教えてください。

[usao]

既に説明されているように

>a[MAX] が bi() 内の自動変数であるため、bi() が呼び出されるたびに
>領域が確保され、初期化が行われないため、ゴミが入っているから

でしょう．

bi(0) で a[0]=0 にしても
bi(1)でのa[0]が0に初期化されているわけではないです．
（bi(0), bi(1), bi(2), ..., bi(n-1) の全てにおいて，ローカル変数は互いに異なる変数ですよ）

コード:

//f()からg()を呼ぶ例
void f()
{
  int a = 10;
  g();
  //ここに来たとき，aの値は10． ( g()によらない )
}

void g()
{
  int a;  //このaはf()の中のaとは違うものなので，この時点で値は不定
  a = 6;
}

というのはわかりますよね．再帰だろうがこれと同様です．

コード:

void f( int i )
{
  int a[3];
  if( i>=3 )return;
  a[i] = 10;
  f( i+1 );  //←これが，現在のa[]に影響を与えることはない
  //ここにきたとき，a[]の内容は { i番目の要素が10,　他は不定 }です．
}

int main()
{
  f(0);
  ...
}

[box]

その説明は間違っています。

当たらずとも遠からず、ということにしといてください。

[epsilon]

皆様のおかげで、納得のいくプログラムが書けました。本当にありがとうございました。