dynamic_01_knapsack.cpp

背包的动态规划算法.rar

// Dynamic_01_knapsack.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//动态规划0-1背包问题
const int ww=20;
const int n=3;
int v[n+1],w[n+1];
int c[n+1][ww+1];
void dynamic_0_1_knapsack(int v[],int w[],int n,int ww)
{
	int i,j;
	
	for(j=0;j<=ww;j++)
		c[0][j]=0;
	for(i=1;i<=n;i++)
	{
		c[i][0]=0;
		for(j=1;j<ww;j++)
		{
			if(w[i]<=j)
				if((v[i]+c[i-1][j-w[i]])>c[i-1][j])
					c[i][j]=v[i]+c[i-1][j-w[i]];
				else
					c[i][j]=c[i-1][j];
			else
				c[i][j]=c[i-1][j];
		}
	}
	cout<<c[i-1][j-1]<<endl;
}

int main(int argc, char* argv[])
{
	v[1]=25; v[2]=24; v[3]=15;
	w[1]=18; w[2]=15; w[3]=10; 
	dynamic_0_1_knapsack(v,w,n,ww);
	return 0;
}