动态规划实现0-1背包问题

0-1背包问题：给定n中物品和一些背包，物品i的重量是wi，其价值是vi，背包的容量为c。选择装入背包的物品，使得装入背包中物品的总价值最大。

在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包（1）或不装入背包（0），不能将物品i装入背包多次，也不能只装入部分的物品i。

设所给问题的子问题最优值为m（i，j）（即背包容量为j，可选择物品为i，i+1，...,n）；用二维数组m[][]存储m（i，j）的相应值，最后给出相应的最优解（0，x1,x2,x3,...xn）

#include<stdio.h>

int Min(int a, int b)
{
	return a < b ? a : b;
}

int Max(int a, int b)
{
	return a > b ? a : b;
}

void Knapsack(int v[],int lenght_v, int w[], int c, int m[][11])
{
	const int n = lenght_v - 1;
	int jMax = Min(w[n] - 1, c);
	for (int j = 0; j <= jMax; j++)
	{
		m[n][j] = 0;				//边界（装不下）
	}
	for (int j = w[n]; j <= c; j++)
	{
		m[n][j] = v[n];
	}

	for (int i = n - 1; i > 1; i--)		//从n-1到2
	{
		jMax = Min(w[i] - 1, c);
		for (int j = 0; j <= jMax; j++)
		{
			m[i][j] = m[i + 1][j];
		}
		for (int j = w[i]; j <= c; j++)
		{
			m[i][j] = Max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
		}
	}
	m[1][c] = m[2][c];
	if (c >= w[1])
	{
		m[1][c] = Max(m[1][c], m[2][c - w[1]] + v[1]);
	}
}

void Traceback(int m[][11], int w[], int lenght_w, int c, int x[])
{
	
	int n = lenght_w - 1; 
	for (int i = 1; i < n; i++)
	{
		if (m[i][c] == m[i + 1][c])
		{
			x[i] = 0;
		}
		else
		{
			x[i] = 1;//1 表示在背包内
			c -= w[i];			
		}
		printf("%d\n",x[i]);
	}
	x[n] = (m[n][c] > 0) ? 1 : 0;
	printf("%d\n", x[n ]);
}

int main()
{
	const int n = 5, c = 10;
	int w[] = { 0, 2, 2, 6, 5, 4 };	//0号下标不记录任何数值
	int v[] = { 0, 6, 3, 5, 4, 6 };	//0号下标不记录任何数值
	int m[n + 1][c + 1] = {};		//0号下标不记录任何数值
	int x[n+1] = {};				//0号下标不记录任何数值
	int length_v = sizeof(v) / sizeof(v[0]);
	int length_w = sizeof(w) / sizeof(w[0]);

	Knapsack( v, length_v, w, c, m);
	Traceback(m, w, length_w,c, x);
	
	return 0;
}
           

所给代码中对于的背包问题中m数组为

i (行)  j(列)	1	2	3	4	5	6	7	8	9	10
5	6	6	6	6	6	6	6
4	6	6	6	6	6	10	10
3	6	6	6	6	6	10	11
2	3	3	6	6	9	9	9	10	11
1	15