动态规划解决0-1背包问题

#include<iostream.h>
#include <stdio.h>
#define M 7

int p=3;  //3个物品
int v[]={0,1,2,5};
int w[]={0,2,3,4};
int c=6;
int m[M][M];   //m>c
int x[4]; //解向量
/*
int p=6;  //3个物品
int v[]={0,100,50,20,10,7,3};
int w[]={0,100,50,20,10,7,3};
int c=163;
int m[M][200];  
int x[7]; //解向量
*/
int min(int a,int b)
{
	return a<b?a:b;
}
int max(int a,int b)
{
	return a>b?a:b;
}

//3  从小问题到大问题计算最优值
//先赋初值，再逐步扩大问题规模 
//求出所有的m[i][j]:　从i,i+1,...,p 重量<=j 的解，最后取　m[1][c] 
void knapsack()
{
	int n=p,i,j;
	int jmax=min(w[n]-1,c);
	for(j=0;j<=jmax;j++)
		m[n][j]=0;
	for(j=w[n];j<=c;j++)
		m[n][j]=v[n];
	    
	for(i=n-1;i>1;i--)
	{
		jmax=min(w[i]-1,c);
		for(j=0;j<=jmax;j++)
			m[i][j]=m[i+1][j];
		for(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];//先假设不放入1
	if(c>=w[1])
		m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
//4  构造最优解
void traceback()
{
	int n=p;
	for(int i=1;i<n;i++)
		if(m[i][c]==m[i+1][c])
			x[i]=0;
		else
		{
			x[i]=1;
			c-=w[i];
		}
	x[n]=(m[n][c]>0)?1:0;//看是否可以放入n
}
void main()
{
	knapsack();
	traceback();
	cout<<m[1][6]<<endl;
	for(int i=1;i<=p;i++)
		cout<<x[i]<<ends;
	cout<<endl;
	int i;
	cin>>i;
}
//
//动态规划(0-1背包)
//1  证明具有最优子结构性质
//2  找递归关系
//3  从小问题到大问题计算最优值
//4  构造最优解
//0-1 knap: recursion(递归式)
//(1)   when j>=w[i]        m[i][j]=max{m[i+1][j],m[i+1][j-w[i]]+v[i]}   m[i][j]: 背包重量为j,可选物品为i,i+1,...,n时可以获得的最大价值
//      when j>=0&&j<w[i]   m[i][j]=m[i+1][j]  (w[i]不能放)
//(2)   when j>w[n]         m[n][j]=v[n]
//      when j>=0&&j<w[n]   m[n][j]=0
//w[i] is integer,c is capacitance,v[i] is the value of object i.