学步园

	。

      我们给出一个待测试用例的完整的0-1背包问题动态规划解法的C语言源码：

#include<stdio.h>
#include<stdlib.h>
void knappsack(int *w,int *v,int c,int n,int m[][10])
{
	int k=n-1;
	int t_v;
	for(int j=0;j<c;j++)
	{
		if(j<w[k]-1)
			m[k][j]=0;
		else 
			m[k][j]=v[k];
	}
	for(int i=k-1;i>=0;i--)
	{
		for(int j=0;j<c;j++)
		{
			if(j<w[i]-1){
				m[i][j]=m[i+1][j];
			}
			else
			{
				int temp,t_v;
				t_v=j-w[i]+1;
				if(t_v>0)
					t_v--;
				temp=m[i+1][t_v]+v[i];
				m[i][j]=temp>m[i+1][j]?temp:m[i+1][j];
			}
		}
	}
	m[0][9]=m[1][9];
	if(c>w[0])
	{
		t_v=m[1][c-w[0]-1]+v[0];
		m[0][9]=t_v>m[1][9]?t_v:m[1][9];
	}
}
void Traceback(int m[][10],int *w,int c,int *x,int n)
{
	for(int i=0;i<n-1;i++)
	{
		if(m[i][c-1]==m[i+1][c-1])
			x[i]=0;
		else
		{
			x[i]=1;
			c-=w[i];
		}
	}
	x[n-1]=(m[n-1][c-1])?1:0;
}
int main()
{
	int n,c,w[5]={2,2,6,5,4},v[5]={6,3,5,4,6},m[5][10],x[5];
	n=5;c=10;
	knappsack(w,v,c,5,m);
	Traceback(m,w,c,x,5);
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<10;j++)
			printf("%3d",m[i][j]);
		printf("\n");
	}
	for(int i=0;i<5;i++)
		printf("%3d",x[i]);
	printf("\n %3d\n",m[0][9]);
}

          计算复杂性分析：从计算m(i,j)的递归式可看出knappsack()需要O(nc)计算时间，而Traceback()需要O(n)的时间，故总体的计算时间复杂度为O(nc)。但有一个潜在的问题，当C>2ⁿ的时候，计算时间变为O(n2ⁿ)反而降低了效率。

        0-1背包问题不能使用贪心算法求解，原因在于贪心选择不能保证背包最后装满，它虽然使得已装入的物品单位容量的价值增大，但空余的空间会使单位价值量降低。总而言之0-1背包问题不具有贪心选择性质。