ナップサック問題

■ダイナミックプログラミング（動的計画法）とは
最適化問題を解くのに効果的な方法。　

具体的には、n個の要素に関する問題の最適解を求めるのに、部分集合であるi個の問題の最適解を覚えておき、
i個から1つ要素を増やした場合、覚えておいた最適解が変化するを調べる。

変化した場合は、それを最適解とし、最終的にn個の問題の最適解を見つけることができるというものだ。

■ナップサック問題
ダイナミックプログラミングの代表的な例題。

入れることのできる重さが決まっているナップサックに、どれだけ無駄がなく詰めきれるかというもの。

今回は、重さと値段があるデータについて、なるべくナップサックの中身が高価格になるようにつめる
という問題に取り組むことにした。

下記がソースです。　ただ、ちょっと今日は忙しかったんで書きなぐった状態です。
気が向いたら、きれいに書きなおそうと思います。

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

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

出力

1000,2100,3100,4500,6100,7100,8200,9200,
   3,   2,   3,   0,   1,   3,   2,   3,
ナップサックに入れるもの
3:DS, 2:PSP, 1:XBOX360,

最終的な最適化表と、求めた買ったナップサックに入れるものです。
DS, PSP, XBOX360 をナップサックに詰めた場合、今回は一番高価になるようです。