动态规划解决0-1背包问题-0-1 knapsack problem.zip

#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.