ナップザック問題

目次

ナップザック問題

今回は、アルゴリズムの例題としてナップザック問題を取り扱います。

価値と大きさを持つ品物が何種類かあり、それを容積の決められたナップザックの中に容積がいっぱいになるまで詰めていきます。
その中で、価値が最も大きくなるような品物の組み合わせを求めます。
すなわち価値の合計が最大でかつ大きさの合計が容積以下である組み合わせを求めます。
このような問題をナップザック問題といいます。

動的計画法

この問題の解法として動的計画法という方法があります。

ナップザックの容積以下の全ての値を最大容積としたとき、それぞれの最大容積に対して品物の種類を増やしながら最大価値を求めていきます。

サンプルコード

以下がサンプルコードです。

#include <stdio.h>

#define MAX_ITEMS 5
#define CAPACITY 7

struct item
{
	char *name;
	unsigned int value;
	unsigned int size;
};

int main(void)
{
	int i, j, temp;
	struct item items[MAX_ITEMS];
	int choices[CAPACITY + 1];
	int maxValues[CAPACITY + 1];

	{
		items[0].name	= "A";
		items[0].size	= 1;
		items[0].value	= 2;

		items[1].name	= "B";
		items[1].size	= 2;
		items[1].value	= 6;

		items[2].name	= "C";
		items[2].size	= 3;
		items[2].value	= 9;

		items[3].name	= "D";
		items[3].size	= 4;
		items[3].value	= 13;

		items[4].name	= "E";
		items[4].size	= 5;
		items[4].value	= 18;
	}

	for (i = 0; i < CAPACITY + 1; i++)
	{
		maxValues[i] = 0;
		choices[i] = -1;
	}
	
	for (i = 0; i < MAX_ITEMS; i++)
	{
		for (j = items[i].size; j < CAPACITY + 1; j++)
		{
			temp = maxValues[j - items[i].size] + items[i].value;
			if (temp > maxValues[j])
			{
				maxValues[j] = temp;
				choices[j] = i;
			}
		}
	}
	

	i = CAPACITY;
	while (choices[i] >= 0)
	{
		printf("%s\n", items[choices[i]].name);
		i -= items[choices[i]].size;
	}
	printf("価値合計:%d\n", maxValues[CAPACITY]);

        return 0;
}

配列choices[i]は、最大容積がiのときの選択したitemsの要素番号、配列maxValues[i]は、最大容積がiのときのその時点での最大価値を格納しています。

二重ループ内が動的計画法のメインです。
各アイテムごとに各最大容量ごとの最大価値を調べています。

(参考:平成29年度応用情報技術者試験午後問題)


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です