动态规划0-1背包.cpp

来自「算法设计分析的一些例子程序....凑字数..凑字数」· C++ 代码 · 共 57 行

#include<iostream>　
using namespace std;
int max(int a,int b)
{
  if(a>b)
	  return a;
  else
	  return b;
}
int min(int a,int b)
{
 if(a>b)
	 return b;
 else
	 return a;
}
void Knapsack(int *v,int *w,int *z,int c,int n,int m[11][6])
{
  int k=min(w[n-1],c);
  for(int i=0;i<k;i++)
	  m[i][n]=0;
  for( i=k;i<=c;i++)
	  m[i][n]=v[n-1];
  for(int j=n-1;j>0;j--)
  {
    k=min(w[j-1],c);
	for(int i=0;i<k;i++)
		m[i][j]=m[i][j+1];
	for( i=k;i<=c;i++)
		m[i][j]=max(m[i][j+1],m[i-w[j-1]][j+1]+v[j-1]);
  }
  for(i=0;i<n;i++)
  {
	  if(m[c][i+1]==m[c][i+2])
		  z[i]=0;
	  else
	  {
		  z[i]=1;
		  c=c-w[i];
	  }
  }
	  
}
void main()
{
  int n=5,c=10;
  int v[5]={6,3,5,4,6},w[5]={2,2,6,5,4},z[5]={0};
  int m[11][6]={0};
  Knapsack(v,w,z,c,n,m);
  cout<<"最大价值为："<<m[10][1]<<endl;
  for(int i=0;i<n;i++)
  {
	  cout<<z[i]<<"  ";
  }
  cout<<endl;
}