ナップサック問題の解法（完全列挙）

完全列挙のプログラムで下記のコードで、探索の中で暫定解よりも価値が低い組合せが見込まれる場合は枝刈りを行い、それが見えるようにしたいのですが、今のままでは暫定解しか表示されません。
どのように書けばいいのでしょうか。コンパイラはGCCを使用しています。丸投げする形になってしまい申し訳ありません。どうかよろしくお願いします。


ソースコード
ーーーーーーーーーーーーーーーーーーーーーーーーーーー
#include<stdio.h>
#include<stdlib.h>

#define KNAP_MAX 30
#define ITEM_NUM 10
#define N 50

int a[N]={0}, u[N + 1];

int weight[ITEM_NUM];

int value[ITEM_NUM];

int maxSelect[ITEM_NUM];

int maxValue = 0;

int totalWeight = 0;

int count;
FILE *fin;


void search(int itemNum, int sumWeight, int sumValue,int ch)
{
int k;
int select[ITEM_NUM];

if(sumWeight > KNAP_MAX)
{
return ;
}
if(itemNum < ITEM_NUM)
{
search(itemNum + 1, sumWeight, sumValue, ch);
a[ch]=itemNum+1;
search(itemNum + 1, sumWeight + weight[itemNum], sumValue + value[itemNum], ch+1);
a[ch]=0;
}
else
{
if(sumValue > maxValue)
{
maxValue = sumValue;
totalWeight = sumWeight;
for(k = 0; k < ITEM_NUM; k++)
printf("%d", a[k]);
printf("(%d円, %dkg)", sumValue, sumWeight);
printf("→暫定解更新(%d円, %dkg)\n", maxValue, totalWeight);
}
}
}

int main() {

if((fin=fopen("weight10.dat","r"))==NULL){
printf("weight10.dat can not open\n");
exit(1);
}
for(count=0;count<ITEM_NUM;count++)fscanf(fin,"%d\n",&weight[count]);
fclose(fin);

if((fin=fopen("value10.dat","r"))==NULL){
printf("value10.dat can not open\n");
exit(1);
}
for(count=0;count<ITEM_NUM;count++)fscanf(fin,"%d\n",&value[count]);
fclose(fin);

printf("< 列挙 >\n\n");

search(0, 0, 0, 0);

printf("\n< 全探索で得られた解 >\n");

printf("重量の合計値 = %dkg\n", totalWeight);
printf("価値の最大値 = %d円\n", maxValue);

return 0;
}

/*-----------------------------------------------------
value10.dat
1198
1011
814
764
816
994
1391
615
1398
924

weight10.dat
3
10
8
9
7
4
7
5
8
2
924
-----------------------------------------------------*/

質問者からの補足コメント

• 判定はif文での判定をさせたいと考えています。また、weight10.datの最後の924は誤りです。申し訳ございません。

    補足日時：2020/01/31 03:30

No.1 回答者： Tacosan 回答日時： 2020/01/31 00:18

「探索の中で暫定解よりも価値が低い組合せが見込まれる場合は枝刈りを行い、それが見えるようにしたい」というなら, 少なくとも「暫定解よりも価値が低い組合せが見込まれる」かどうかを判定しないといけない.

どうやって判定しますか?

この回答へのお礼

判定方法としてはif文で暫定解より大きいか、そうでないかを判定させたいと考えています。

お礼日時：2020/01/31 03:28

No.2 回答者： Tacosan 回答日時： 2020/01/31 23:22

普通の人は if を使うだろうけど (while でできるかなぁ...), そんなことを聞きたいんじゃない.

どのような条件で判定する? 「自分がやる」としたらどうする?

この回答へのお礼

自分としてはナップサックの容量以下という条件の元で価値が大きくなった組み合わせを順次暫定解として保存、その後の探索で列挙の番号に応じて品物を足していく際に暫定解よりも価値が大きくならないようならその場で探索を止めて、別の組み合わせを調べるようにします。

お礼日時：2020/02/03 15:42

No.3 ベストアンサー 回答者： Tacosan 回答日時： 2020/02/05 03:48

「暫定解よりも価値が大きくならない」って, どうやったら判定できるんだろうね.

ちなみに, 「わからん」ところは適切な名前の関数を作っておくとなんとなくプログラムになったような気になれる. 「気になれる」だけだけど.

この回答へのお礼

1度条件や必要な関数について確認してみます。今回はありがとうございました。

お礼日時：2020/02/06 10:02