Ｃ言語でナップザック問題 総当たりで悩んでいます

Question

前提・実現したいこと

ｃ言語でナップザック問題を解きたい
重さと価値がそれぞれ w_i, v_i であるような n 個の品物があり、重さの総和がWを超えないように選んだときの価値の総和のの最大値を求める
例1）n = 4、(w, v) = { (2, 3), (1, 2), (3, 4), (2, 2) }、W = 5 → 出力　7
例2）n = 3、(w, v) = { (2, 2), (2, 1), (1, 1), }、W = 5 → 出力　4

発生している問題

組み合わせを総当たりするという部分で躓いています

上記の(例1)でいえば(2,3)(3,4)で済んでいますが、
(例2)ならば(2,2), (2,1), (1,1)になります。取る値が入力次第で変わるのでfor文をどのように回せばいいかがわかりません

考えている流れとしては
総和を超えない組み合わせを探す→価値の最大値を求める→出力です
今回は総当たりの部分のヒントをいただきたいです

該当のソースコード

#include <stdlib.h>
int main(void)
{
    int n=0;//品物の個数
    int w=0;//求める総和
    int w_i[100000];//重さ
    int v_i[100000];//価値
    printf("品物の数");
    scanf("%d",&n);
    if(1 <= n && n <= 100){
     }else{
        printf("ERROR!\n");
        exit(0);
    }
    printf("重さと価値\n");
    for(int i=0; i<n; i++ ){
            scanf("%d , %d",&w_i[i],&v_i[i]); 
              if( 1 <= w_i[i],v_i[i] && w_i[i],v_i[i] <= 100){
        }else{
                printf("ERROR!\n");
                exit(0);
        }
    }
    printf("求める総和");
    scanf("%d",&w);
    if(1 <= w && w <= 10000){
     }else{
        printf("ERROR!\n");
        exit(0);
    }

 /*  本体部分何も書けてないです  */
    
    return 0;
}

試したこと

for(int j=0;j<n;j++){
    for(int k=1;k<n;k++){
        for(int l=2;l<n;l++){
            ・・・・
        }
    }
}

のようにforで総当たりを考えましたがこれだと取る値の数が限られるので没

補足情報（FW/ツールのバージョンなど）

Visual Studio Codeを使用しています。

Answer 1

n個のアイテムに対し、持つ、持たないの組合せは全部で何通りありますか?

そう、2^n通りですね。

後はループを回すだけです。

ググるためのキーワードは、ビット操作、インクリメントです。

追記：具体化するとどうなる? とご指摘を頂いたので、あまり本人のためにならないかもですが、コードを書きます。

#include <stdlib.h>

int main(void)
{
    int n;// up to 32
    int maxweight;
    int weight[32];
    int value[32];
    int maxvalue = 0;
    int i, e, j, w, v;

    printf("品物の数");
    scanf("%d", &n);
    if(n < 1 || 32 < n){
        printf("ERROR!\n");
        exit(0);
    }
    printf("重さと価値\n");
    for(i = 0; i < n; i++){
        scanf("%d , %d", &weight[i], &value[i]); 
        if( weight[i] < 1 || 100 < weight[i] || value[i] < 1 || 100 < value[i]){
            printf("ERROR!\n");
            exit(0);
        }
    }
    printf("求める総和");
    scanf("%d", &maxweight);
    if(maxweight < 1 || 10000 < maxweight){
        printf("ERROR!\n");
        exit(0);
    }

    e = 1 << n;
    for(i = 1; i != e;){
        w = 0;
        v = 0;
        for(j = 0; j < n; j++){
            if(i & (1 << (n - 1 - j))){
                w += weight[j];
                v += value[j];
            }
        }
        if(w > maxweight){
            i += (i & -i);
        }
        else{
            if(v > maxvalue){
                maxvalue = v;
            }
            i++;
        }
    }

    return 0;
}

Comments

[Senri551853]

回答ありがとうございます。キーワードを検索してもパッとしなかったので具体的に書いてくださって助かりました

追記 ビットを1ずらす理由がよくわからないのですがご教授していただけませんか…？

追記追記 2^n 回を実現？しているということであってますか？

[majiponi]

rubato6809さんがほぼ補足してくださいましたが、概ね予想通りです。一言だけ補足すると、例えば「1番と3番」で制限重量を超えていたら、「1番と3番と4番」は調べる必要がありませんよね? そのためにi += (i & -i);という一行があります。

[rubato6809]

Senri551853さん、majiponiさん、評価ありがとうございます。
for ループで ksack++ とすべき所、「++」が抜けてたことに、BAいただいてから気づきました。修正しました。

Answer 2

majiponiさんの反応が無いまま、BAが付いてないので出しゃばります。

n個のアイテムに対し、持つ、持たないの組合せは全部で 2^n通り、後はループを回すだけ

アイテム数４の { (2, 3), (1, 2), (3, 4), (2, 2) } を例にすると、2 ^ 4 = 16 です。ここで、

アイテム	(2, 3)	(1, 2)	(3, 4)	(2, 2)
対応する値	1	2	4	8

と対応させます。すると、 (2, 3) と (3, 4) をナップサックに詰めることを 5 (== 1 + 4) という値で表すことができます。値が０ならナップサックは空、15（==1+2+4+8）なら４アイテム全てを詰める、という意味になります。
つまり、４個のアイテム全ての組合せは０～１５という１６種類の値で表現できることになり

    for (ksack = 0; ksack < 16; ksack++) {
        // ksackの値＝アイテムの組合せを評価する

という格好の、一重の for ループが総当たり検査になるのです。

ビットを1ずらす理由がよくわからない

1, 2, 4, 8 という値は、それぞれ２のべき乗です。
bit = 1 から始めて、bit <<= 1 でビットをひとつずつずらすと、
bit の値は 1, 2, 4, 8 ... と変化します。そこで
if ((ksack & bit) != 0) と、AND演算（というビット演算）によって、ksack にどのアイテムが含まれるかを判定することに使えます。

※以上、私は majiponi さんと違うコードで試したので、説明中のコード表記が異なりますが、言いたいことは伝わるだろうと思います。

Comments

[majiponi]

説明上手いなあ…(現役国語講師が負けててどうするって気もしますが)

[rubato6809]

for ループで ksack++ とすべき所、「++」が抜けてたことに、BAいただいてから気づきました。修正しました。

Answer 3

例2）n = 3、(w, v) = { (2, 2), (2, 1), (1, 1), }、W = 5 → 出力　7

この場合、出力は 4 ではないのですか？

取る値が入力次第で変わるのでfor文をどのように回せばいいかがわかりません

再帰呼出しを使うといいでしょう。

各品物を選ぶかどうかを総当たりでやると、すごい数になります。
選んだものの重さの総和が W を超えたら、次の品物には行かない
ようにすることで、場合の数を減らすことができます。

#include <stdio.h>

typedef struct { int w_i, v_i; } Goods;

Goods *g;
int n, W, w, v, max_v;

void knapsack(int i)
{
	if (i < n) {
		w += g[i].w_i;
		if (w <= W)
			v += g[i].v_i, knapsack(i + 1), v -= g[i].v_i;
		w -= g[i].w_i;
		knapsack(i + 1);
	}
	else if (v > max_v) max_v = v;
}

int main(void)
{
	Goods g1[4] = { {2, 3}, {1, 2}, {3, 4}, {2, 2} };
	g = g1, n = 4, W = 5, max_v = 0;
	knapsack(0);
	printf("%d\n", max_v);

	Goods g2[3] = { {2, 2}, {2, 1}, {1, 1} };
	g = g2, n = 3, W = 5, max_v = 0;;
	knapsack(0);
	printf("%d\n", max_v);
}

Comments

[Senri551853]

回答ありがとうございます。for文を使うことにとらわれていたので、こういうやり方もあるのかと驚いています。再帰について改めて勉強したいと思います
>>この場合、出力は4ではないのですか？
仰る通りです、記載ミスでした…

Answer 4

for文でやることにとらわれているようですがfor文は使いません。やり方はkazuma-s様と同じになりますが、ナップザック問題は再帰で解くのがいいようです。また、majiponiさんがビット操作を使うと仰っていますが、これだけで分かったらあなたは天才だと思います。

やり方としましては、まず答えを返してくれる予定の関数を宣言して、その中で、i番目の商品をナップザックに「入れる」or「入れない」の2通りに分けます。これがおそらくmajiponiさんの仰るビット操作だと思います。この関数を再帰させます。ナップザックは総当たりしか方法がないという説が主流なようです。この先は答えなのでヒントだけ欲しいならばこの先は読まないでください。

//関数だけ

int knapsack(int i, int w){   //iはi番目の商品、wはi番目の商品の処理の時の残りの重さ
        if(i >= n)            return 0; //要素数を超えた商品は存在しない
        if(w - w_i[i] < 0)    return knapsack(i + 1, w); //重さの制限を超えたときは商品iは選ばない

        int v1, v2;
        v1 = knapsack(i + 1, w);                     //商品iは取らなかった時の最大価値
        v2 = v_i[i] + knapsack(i + 1, w - w_i[i]);   //商品iを取った時の最大価値

        return v1 > v2 ? v1 : v2;
}

Comments

[kazuma-s]

そのプログラムでは、
n = 3、(w, v) = { (1, 2), (4, 1), (2, 3), }、W = 3 → 出力　5
となるべきところが 2 になりませんか？

[tometome]

ご指摘ありがとうございます。気を付けなければいけませんね...

[Senri551853]

回答ありがとうございます。
forで総当たりしなくても実現できるのですね。再帰の考え方がいまいちわからなくて触れずにいたのですが改めて勉強したいと思います。