动态规划背包问题（例题）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
using namespace std;
int val[]={ 
   0,3,4,5,6};
int vol[]={ 
   0,2,3,4,5};
int f[5][9];
bool flag[5]={ 
   true};
//背包的容积为8
//物品编号1,2,3,4
//物品容积2,3,4,5
//物品体积3,4,5,6 

int maxvalue(){ 
   
	
	for(int i=0; i<=4; i++){ 
   
		for(int j=0; j<=8; j++){ 
   
			if(i==0 || j==0){ 
   
				f[i][j]=0; 
			}else{ 
   
				if(vol[i]<=j)
					f[i][j]=max(f[i-1][j], f[i-1][j-vol[i]]+val[i]);
				else{ 
   
					f[i][j]=f[i-1][j];
				}
			}
		}
	}
	
} 

int back(int i, int j){ 
   
	if(i==0){ 
   
		for(int i=1; i<5; i++){ 
   
			if(flag[i]) cout<<i<<" ";
		}
	}
	if(f[i][j]==f[i-1][j]){ 
   
		back(i-1,j);
	}
	else if(f[i][j]==f[i-1][j-vol[i]]+val[i]){ 
   
		flag[i]=true;
		back(i-1,j-vol[i]);
	}
}

int main(){ 
   
	maxvalue();
	for(int i=0; i<=4; i++){ 
   
		for(int j=0; j<=8; j++){ 
   
			printf("%4d",f[i][j]);
		}
		cout<<endl;
	}
	
	back(4,8);
	return 0;
}