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

[peko]

以前ナップサック問題についてのトピックを立てたものです。プログラミング初心者です。
goods[]を6個から37個に増やしたところ、動作終了と出てしまいます。

品物は重複をしないように選択されるようにしたいのですが、どのように変更すればよろしいでしょうか？
ご指導お願いします。

コード:

#include <stdio.h>
#include <memory.h>

// 適当にナップサックに入れる商品リストを定義する
struct Goods
{
	int  no;
	char name[80];
	int  weight;    //各要素の重量
	int  price;	    //価値を最大にしたい
}goods[] = {
//価値は男女合計値
	{1 ,"a"	 ,21 , 9},
	{2 ,"b"		 ,23 , 28},
	{3 ,"c"		 ,20 , 8},
	{4 ,"d"		 ,34 , 14},
	{5 ,"e"   ,18 , 2},
	{6,"f",43, 56},
	{7,"g",24, 6},
	{8,"h",35, 5},
	{9,"i",21,4},
	{10,"j",25, 3},
	{11,"k",39, 4},
	{12,"l",37, 5},
	{13,"m",45, 40},
	{14,"n",20, 12},
	{15,"o",12, 3},
	{16,"p",47, 40},
	{17,"q",44, 17},
	{18,"r",173, 73},
	{19,"s",133, 63},
	{20,"t",48, 9},
	{21,"u",13, 3},
	{22,"v",13, 8},
	{23,"w",11, 8},
	{24,"x",13, 4},
	{25,"y",92, 40},
	{26,"z",132, 70},
	{27,"aa",38, 8},
	{28,"bb",29, 7},
	{29,"cc",59, 21},
	{30,"dd",104, 51},
	{31,"ee",8, 2},
	{32,"ff",76, 54},
	{33,"gg",37, 14},
	{34,"hh",35, 8},
	{35,"ii",18, 4},
	{36,"jj",105, 25},
	{37,"kk",46, 8},
};

void main()
{
	const int KNAP_SIZE_MAX = 600;	// ナップサックに入る最大重量
	    int item[KNAP_SIZE_MAX+1]  = {0};
    int value[KNAP_SIZE_MAX+1] = {0};
    int item_index[KNAP_SIZE_MAX+1] = {0}; // 入れた商品の添字+1
 
    for( int j=0; j<sizeof(goods)/sizeof(Goods); j++ ){ // 商品分のループ
        for( int i=1; i<=KNAP_SIZE_MAX; i++ ){          // ナップサックサイズのループ
            int knapSpace = i - goods[j].weight;
            if( knapSpace >=0 && knapSpace <= KNAP_SIZE_MAX ){
                int newValue = value[knapSpace] + goods[j].price;
                if( newValue > value[i] && item_index[knapSpace] < j + 1){ // 今の候補よりいい感じ、かつ前に入れた商品より先の商品のみ入れる
                    value[i] = newValue;
                    item[i]  = goods[j].no;
                    item_index[i] = j + 1;
                }
            }
        }
    }


	// 結果表示
	for( int i=1; i <= KNAP_SIZE_MAX; i++ ){
		printf( "%4d,", value[i] );
	}
	printf("\n");	
	for( int i=1; i <= KNAP_SIZE_MAX; i++ ){
		printf( "%4d,", item[i] );
	}
	printf("\n");	

	printf("ナップサックに入れるもの\n");

	int count = 0;
	int inItem[KNAP_SIZE_MAX];	// ナップサックに入れる最適な商品
	memset( inItem, -1, sizeof(inItem) );

	int nokori   = KNAP_SIZE_MAX;	// ナップサックの残りサイズ

	do{
		int inItem_ = nokori;
		nokori = nokori - goods[ item[nokori] ].weight;		
		inItem[count++] = item[inItem_]; 
	}while( nokori != 0 );

	for( int i=0; i < KNAP_SIZE_MAX; i++ ){
		if( inItem[i] > -1 ){
			printf( "%d:%s, ", inItem[i], goods[ inItem[i] ].name );
		}
	}
	printf("\n");
}

[みけCAT]

とりあえず、現状のコードは
・構造体を表すためにstruct GoodsではなくGoodsが使われている
・可変長配列が初期化されている
ためにC言語としてはコンパイルが通らず、
・グローバルにvoid main()が定義されている
ためにC++としてもコンパイルが通りません。
まずはコンパイルが通るコードにしましょう。
void main()をint main()にすると、Segmentation Faultが確認できました。

[みけCAT]

94行目でgoods[ item[nokori] ].weightを参照していますが、itemの要素には66行目でgoods[j].noが代入されており、
これは配列goodsにおいてgoods[j]が格納されている添字とは異なるので、まずそうですね。
また、容量を使い切らない場合も考えないといけません。
void main()をint main()にした上で、92行目～96行目を

コード:

    do{
        int inItem_ = nokori;
        if (item[nokori] > 0) {
            nokori = nokori - goods[ item[nokori] - 1 ].weight;
        } else {
            break;
        }
        inItem[count++] = item[inItem_]; 
    }while( nokori != 0 );

とすると、

コード:

   0,   0,   0,   0,   0,   0,   0,   2,   2,   2,   8,   8,   8,   8,   8,   8,
   8,   8,  10,  12,  12,  12,  28,  28,  28,  28,  28,  28,  28,  28,  30,  30,
  30,  36,  36,  36,  36,  36,  36,  36,  36,  38,  56,  56,  56,  56,  56,  56,
  56,  56,  58,  58,  58,  64,  64,  64,  64,  64,  64,  64,  64,  66,  68,  68,
  68,  84,  84,  84,  84,  84,  84,  84,  84,  86,  86,  86,  92,  92,  92,  92,
  92,  92,  92,  92,  94,  96,  96,  96,  96, 100, 100, 100, 100, 100, 100, 100,
 104, 104, 104, 104, 104, 104, 104, 104, 106, 106, 106, 108, 108, 112, 124, 124,
 124, 124, 124, 124, 124, 124, 126, 126, 126, 132, 132, 132, 132, 132, 132, 132,
 132, 134, 136, 136, 136, 136, 140, 140, 140, 140, 140, 140, 140, 144, 144, 144,
 144, 144, 144, 144, 144, 146, 146, 146, 146, 146, 152, 152, 152, 164, 164, 164,
 164, 164, 164, 164, 164, 166, 166, 166, 172, 172, 172, 172, 172, 172, 172, 172,
 174, 176, 176, 176, 176, 180, 180, 180, 180, 180, 180, 180, 184, 184, 184, 184,
 184, 184, 184, 184, 186, 186, 186, 186, 186, 192, 192, 192, 192, 192, 192, 192,
 192, 194, 194, 194, 194, 194, 196, 196, 196, 198, 198, 198, 198, 198, 198, 198,
 198, 200, 200, 200, 200, 200, 206, 206, 206, 218, 218, 218, 218, 218, 218, 218,
 218, 220, 220, 220, 226, 226, 226, 226, 226, 226, 226, 226, 228, 230, 230, 230,
 230, 234, 234, 234, 234, 234, 234, 234, 238, 238, 238, 238, 238, 238, 238, 238,
 240, 240, 240, 240, 240, 246, 246, 246, 246, 246, 246, 246, 246, 248, 248, 248,
 248, 248, 250, 250, 250, 244, 248, 250, 250, 250, 252, 252, 252, 252, 252, 252,
 252, 252, 252, 252, 254, 254, 254, 254, 254, 254, 260, 260, 260, 260, 260, 260,
 260, 260, 262, 262, 262, 262, 262, 264, 264, 264, 258, 258, 264, 264, 264, 266,
 266, 266, 264, 264, 266, 266, 266, 266, 266, 268, 268, 268, 266, 268, 268, 268,
 268, 270, 270, 270, 268, 270, 270, 270, 270, 270, 272, 272, 272, 271, 271, 272,
 272, 289, 289, 289, 289, 290, 273, 276, 276, 296, 296, 296, 296, 297, 297, 297,
 298, 300, 300, 300, 300, 304, 304, 304, 304, 304, 304, 304, 308, 308, 308, 308,
 308, 308, 308, 308, 310, 310, 310, 310, 310, 316, 316, 316, 316, 316, 316, 316,
 316, 318, 318, 318, 318, 318, 320, 320, 320, 320, 320, 320, 320, 320, 322, 322,
 322, 322, 322, 322, 322, 322, 323, 323, 325, 325, 325, 325, 325, 324, 330, 330,
 330, 330, 330, 330, 330, 330, 332, 332, 332, 332, 332, 334, 334, 334, 334, 334,
 334, 334, 334, 336, 336, 336, 336, 336, 336, 336, 336, 337, 337, 339, 339, 339,
 339, 339, 338, 338, 338, 340, 340, 340, 340, 340, 340, 340, 340, 341, 342, 343,
 343, 343, 343, 343, 342, 342, 344, 344, 344, 344, 344, 344, 344, 344, 345, 345,
 347, 347, 347, 347, 347, 344, 346, 346, 348, 369, 369, 369, 369, 369, 348, 348,
 349, 371, 371, 371, 371, 371, 373, 373, 373, 373, 373, 373, 373, 373, 374, 374,
 376, 376, 376, 376, 376, 376, 376, 376, 378, 378, 378, 378, 378, 384, 384, 384,
 384, 384, 384, 384, 384, 386, 386, 386, 386, 386, 388, 388, 388, 387, 387, 388,
 388, 390, 390, 390, 390, 391, 391, 391, 390, 392, 392, 390, 398, 398, 395, 395,
 399, 392, 398, 398, 400, 398, 398, 398,
   0,   0,   0,   0,   0,   0,   0,  31,  31,  31,  23,  23,  22,  22,  22,  22,
  22,  22,  31,  14,  14,  14,   2,   2,   2,   2,   2,   2,   2,   2,  31,  31,
  31,  23,  23,  22,  22,  22,  22,  22,  22,  31,   6,   6,   6,   6,   6,   6,
   6,   6,  31,  31,  31,  23,  23,  22,  22,  22,  22,  22,  22,  31,  14,  14,
  14,   6,   6,   6,   6,   6,   6,   6,   6,  31,  31,  31,  23,  23,  22,  22,
  22,  22,  22,  22,  31,  14,  14,  13,  13,  23,  23,  23,  23,  23,  23,  23,
  23,  23,  22,  22,  22,  22,  22,  22,  31,  31,  31,  14,  14,  23,  13,  13,
  13,  13,  13,  13,  13,  13,  31,  31,  31,  23,  23,  22,  22,  22,  22,  22,
  22,  31,  14,  14,  14,  14,  23,  23,  23,  23,  23,  23,  23,  23,  23,  22,
  22,  22,  22,  22,  22,  31,  31,  31,  31,  31,  23,  23,  23,  16,  16,  16,
  16,  16,  16,  16,  16,  31,  31,  31,  23,  23,  22,  22,  22,  22,  22,  22,
  31,  16,  16,  16,  16,  23,  23,  23,  23,  23,  23,  23,  23,  23,  22,  22,
  22,  22,  22,  22,  31,  31,  31,  31,  31,  23,  23,  23,  23,  23,  23,  23,
  23,  31,  31,  31,  31,  31,  24,  24,  24,  32,  32,  32,  32,  32,  31,  31,
  31,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  33,  33,  35,  35,  35,  32,  32,  32,  33,  33,  33,
  33,  33,  33,  33,  35,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,
  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  35,  35,  35,  35,  35,  33,
  33,  33,  35,  35,  35,  35,  35,  35,  35,  35,  35,  35,  26,  34,  34,  34,
  34,  35,  35,  35,  31,  34,  34,  34,  34,  34,  34,  34,  34,  26,  26,  35,
  35,  32,  32,  32,  32,  32,  31,  33,  33,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  33,  33,  33,
  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,
  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,  33,
  33,  33,  34,  34,  34,  35,  35,  35,  35,  34,  34,  34,  34,  35,  34,  35,
  35,  35,  35,  35,  34,  34,  34,  34,  34,  34,  34,  34,  34,  34,  34,  34,
  34,  34,  34,  34,  34,  37,  35,  35,  35,  32,  32,  32,  32,  32,  35,  35,
  35,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  33,  33,  35,
  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  32,  33,  32,  32,  32,  32,
  32,  33,  33,  33,  32,  33,  33,  33,
ナップサックに入れるもの
33:hh, 32:gg, 35:jj, 33:hh, 32:gg, 35:jj, 33:hh, 32:gg, 31:ff, 24:y, 23:x, 22:w,
 16:q, 14:o, 13:n, 6:g, 2:c,

と出力されました。
重複しているので、そこはまた考える必要がありそうですね。

[peko]

返信ありがとうございます。

ご回答していただいた上で大変申し訳ないのですが、重複しないようにするには
どのようにすればよろしいでしょうか？

[みけCAT]

重複してしまう原因は、前のアイテムをチェックした後、次のアイテムを見た時に、
その容量が後で使われているかどうかをチェックせずに更新してしまうことのようですね。

失敗の原因

nappusakku-gekitui-20171217.png (1.89 KiB) 閲覧数: 3418 回

例えば、

コード:

goods[] = {
//価値は男女合計値
    {1 ,"a",10  , 5},
    {2 ,"b",5 , 5},
    {3 ,"c",7 , 10},
    {4 ,"d",3 , 10},
};

    const int KNAP_SIZE_MAX = 22;  // ナップサックに入る最大重量

とすると撃墜できるようです。
従って、これを解決すれば重複を防げるでしょう。
例えば、解を容量が同じなら同じ場所に保存するのではなく、
容量と前に使ったアイテムの組を用いて保存するようにするとよさそうだと思います。
例えばこうすると、少なくとも今回用意したテストケースでは重複しなくなりました。
このコードには、「アイテムの番号」と「アイテムの添字(配列上の位置)」を別に管理する修正も入れています。

コード:

#include <stdio.h>
#include <memory.h>

#ifndef TESTCASE
#define TESTCASE 2
#endif

// 適当にナップサックに入れる商品リストを定義する
struct Goods
{
    int  no;
    char name[80];
    int  weight;    //各要素の重量
    int  price;     //価値を最大にしたい
}goods[] = {
//価値は男女合計値
#if TESTCASE == 1
    {1 ,"a",10  , 5},
    {2 ,"b",5 , 5},
    {3 ,"c",7 , 10},
    {4 ,"d",3 , 10},
#else
    {1 ,"a"  ,21 , 9},
    {2 ,"b"      ,23 , 28},
    {3 ,"c"      ,20 , 8},
    {4 ,"d"      ,34 , 14},
    {5 ,"e"   ,18 , 2},
    {6,"f",43, 56},
    {7,"g",24, 6},
    {8,"h",35, 5},
    {9,"i",21,4},
    {10,"j",25, 3},
    {11,"k",39, 4},
    {12,"l",37, 5},
    {13,"m",45, 40},
    {14,"n",20, 12},
    {15,"o",12, 3},
    {16,"p",47, 40},
    {17,"q",44, 17},
    {18,"r",173, 73},
    {19,"s",133, 63},
    {20,"t",48, 9},
    {21,"u",13, 3},
    {22,"v",13, 8},
    {23,"w",11, 8},
    {24,"x",13, 4},
    {25,"y",92, 40},
    {26,"z",132, 70},
    {27,"aa",38, 8},
    {28,"bb",29, 7},
    {29,"cc",59, 21},
    {30,"dd",104, 51},
    {31,"ee",8, 2},
    {32,"ff",76, 54},
    {33,"gg",37, 14},
    {34,"hh",35, 8},
    {35,"ii",18, 4},
    {36,"jj",105, 25},
    {37,"kk",46, 8},
#endif
};

int main()
{
#if TESTCASE == 1
    const int KNAP_SIZE_MAX = 22;  // ナップサックに入る最大重量
#else
    const int KNAP_SIZE_MAX = 600;  // ナップサックに入る最大重量
#endif
    const int ITEM_SIZE = sizeof(goods)/sizeof(Goods);
    int item[ITEM_SIZE+1][KNAP_SIZE_MAX+1]  = {{0}};
    int value[ITEM_SIZE+1][KNAP_SIZE_MAX+1] = {{0}};
    int item_index[ITEM_SIZE+1][KNAP_SIZE_MAX+1] = {{0}}; // 入れた商品の添字+1

    for( int j=1; j<=ITEM_SIZE; j++ ){ // 商品分のループ
        for( int i=1; i<=KNAP_SIZE_MAX; i++ ){          // ナップサックサイズのループ
            int knapSpace = i - goods[j - 1].weight;
            if( knapSpace >=0 && knapSpace <= KNAP_SIZE_MAX ){
                int newValue = value[j - 1][knapSpace] + goods[j - 1].price;
                if( newValue > value[j - 1][i]){ // 今の候補よりいい感じ
                    value[j][i] = newValue;
                    item[j][i]  = goods[j - 1].no;
                    item_index[j][i] = j;
                } else { // 現状維持
                    value[j][i] = value[j - 1][i];
                    item[j][i] = item[j - 1][i];
                    item_index[j][i] = item_index[j - 1][i];
                }
            }
        }
    }


    // 結果表示
    for( int i=1; i <= KNAP_SIZE_MAX; i++ ){
        printf( "%4d,", value[ITEM_SIZE][i] );
    }
    printf("\n");
    for( int i=1; i <= KNAP_SIZE_MAX; i++ ){
        printf( "%4d,", item[ITEM_SIZE][i] );
    }
    printf("\n");

    printf("ナップサックに入れるもの\n");

    int count = 0;
    int inItem[KNAP_SIZE_MAX];  // ナップサックに入れる最適な商品
    int inItem_index[KNAP_SIZE_MAX];  // ナップサックに入れる最適な商品の添字
    memset( inItem, -1, sizeof(inItem) );

    int nokori   = KNAP_SIZE_MAX;   // ナップサックの残りサイズ
    int current_item = ITEM_SIZE; // 今見ている行

    do{
        int inItem_ = nokori;
        int next_item = item_index[current_item][nokori];
        if (next_item > 0) { // アイテムが入っていたら
            nokori = nokori - goods[ next_item - 1 ].weight;
        } else {
            break;
        }
        inItem_index[count] = next_item - 1;
        inItem[count++] = item[current_item][inItem_]; 
        current_item = next_item - 1; // 今取り出したアイテムの1個下から見る
    }while( nokori != 0 );

    for( int i=0; i < KNAP_SIZE_MAX; i++ ){
        if( inItem[i] > -1 ){
            printf( "%d:%s, ", inItem[i], goods[ inItem_index[i] ].name );
        }
    }
    printf("\n");
}

[peko]

丁寧なご指導有難うございました！

また、質問の機会があればよろしくお願いします！