【DP】 0/1 knapsack problem (single copy)

刚刚博客还不能用，现在终于可以了，呵呵，感谢CSDN管理员！

今天中午上课之前，按照书上0/1背包问题的算法思想用C实现了一下。

具体DP思想见 《算法概率》P184 背包问题

附代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int knapsack(int weight[], int value[], int W, int n)
{
	int i, j;
	int w;
	int max_value;

	int** K = (int**)malloc(sizeof(int*) * (W + 1));
	for (i = 0; i < W + 1; i++)
	{
		K[i] = (int*)malloc(sizeof(int) * (n + 1));
	}
	for (i = 0; i <= W; i++)
	{
		K[i][0] = 0;
	}
	for (i = 0; i <= n; i++)
	{
		K[0][i] = 0;
	}
	for (i = 1; i<= n; i++)
	{
		for (w = 1; w <= W; w++)
		{
			if (weight[i - 1] > w)
			{
				K[w][i] = K[w][i - 1];
			}
			else
			{
				int pre_weight = K[w][i - 1];
				int indexW = w - weight[i - 1];
				int indexI = i - 1;
				K[w][i] = max(pre_weight, K[indexW][indexI] + value[i - 1]);
				/*K[w][i] = max(K[w][i - 1], K[w - weight[i]][i - 1] + value[i - 1]);*/
			}
		}
	}

	/*
	for (i = 0; i <= W; i++)
	{
		for (j = 0; j <= n; j++)
			printf("%d ", K[i][j]);
		printf("/n");
	}
	*/
	max_value = K[W][n];

	for (i = 0; i <= W; i++)
	{
		free((void*)K[i]);
	}

	free((void*)K);

	return max_value;
}

int main()
{
	int weight[] = {6, 3, 4, 2};
	int value[] = {30, 14, 16, 9};
	int W = 10; /* weight that bag carries*/
	int n = sizeof(value) / sizeof(int); /*num of bags*/
	int max_value = knapsack(weight, value, W, n);
	printf("max value =%d", max_value);
	return 0;
}