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

[peko]

　プログラミング初心者です。ナップサック問題についての質問です。
ナップサックの容量を10としたとき、選択される品物が
1,XBOX360 1,XBOX360　　となり、品物が重複してしまいます。

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

コード:

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

// 適当にナップサックに入れる商品リストを定義する
struct Goods
{
	int  no;
	char name[80];
	int  weight;    //各要素の重量
	int  price;	    //価値を最大にしたい
}goods[] = {
	{0 ,"Wii"		 ,4 , 4500},
	{1 ,"XBOX360"	 ,5 , 6100},
	{2 ,"PSP"		 ,2 , 2100},
	{3 ,"DS"		 ,1 , 1000},
	{4 ,"PS3"		 ,6 , 5050},
	{5 ,"gamecube"   ,3 , 3000},
};

void main()
{
	const int KNAP_SIZE_MAX = 8;	// ナップサックに入る最大重量
	int	item[KNAP_SIZE_MAX+1]  = {0};
	int value[KNAP_SIZE_MAX+1] = {0};

	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] ){
					value[i] = newValue;
				    item[i]  = goods[j].no;
				 }
			}
		}
	}

	// 結果表示
	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]

まず、このコードはサイズをconstがついた変数で指定している配列の初期化があり、C言語としてはコンパイルが通らないようなので、C++に近いようですね。
そのため、まずはvoid main()をint main()にして、C++としてコンパイルが通るようにするのがいいでしょう。

次に、商品が重複しないようにするには「前に入れた商品より先の商品のみ入れる」ようにするといいでしょう。
具体的には、例えば23行目～37行目を

コード:

	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;
				}
			}
		}
	}

とするといいでしょう。
配列に入れる値を「入れた商品の添字」ではなく「入れた商品の添字+1」にすることで、
「商品を入れていない」と「0番目の商品を入れている」を簡単に区別できるようにしているのがポイントです。

[peko]

有難うございます。
自分の開発環境では何故かvoid main()でもint main()でも正常に動くことが出来ました。
お手数ですが、もし、c言語としてコンパイルを通したい場合は、どのように修正させればよいでしょうか？

[みけCAT]

お手数ですが、もし、c言語としてコンパイルを通したい場合は、どのように修正させればよいでしょうか？

• = {0} の代わりにmemsetで初期化する
• sizeof(Goods) (構造体の大きさ) をsizeof(struct Goods) にする

ですね。

[peko]

有難うございます。