動的計画法によるナップサック問題のアルゴリズム

Knapsack_sample.c

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