01 가방 문제-만력-동적 기획-거슬러 올라가기-분지한계 완전 코드

설명

만력법

#include 
using namespace std;
int weight[100],value[100];		//        
int Path[100],path[100];        //    ，      
int W;   		//     
int N;    		//     
int Max;        //     
int V;          //     
int w;          //     

int func(int i){
	if(i>=N){
		if(V>Max&&w+value[i]<=W){
			Max=V;
			for(int i=0;i>N;
	
	cout<>W;
	
	cout<>weight[i]>>value[i]; 
	
	cout<

동적 기획

#include 
using namespace std;

void func(int weight[],int value[],int W,int n){
	//Dp[i][j],       j ， i             。 
	int Dp[n+1][W+1];
	//     ，    0
	for(int i=0;i<=n;i++){
		Dp[i][0]=0;
	} 
	for(int j=0;j<=W;j++){
		Dp[0][j]=0;
	}
	//       
	for(int i=1;i<=n;i++){
		for(int j=1;j<=W;j++){
			if(j0;i--){
		if(Dp[i][j]>Dp[i-1][j]){
			path[i-1]=1;
			j=j-weight[i-1];
		}else{
			path[i-1]=0;
		}
	} 
	for(int i=0;i>n;
	
	int weight[n],value[n];
	cout<>weight[i]>>value[i]; 
	} 
	cout<>W; 
	
	func(weight,value,W,n);
	
	return 0;
} 

거슬러 올라가다

#include 
using namespace std;
int Path[100];     //Path     ，path     。
void func(int weight[],int value[],int W,int n,int path[],int &Max,int V,int c,int start){
//V      ，c      ，Max           
	if(c<=W){
		//Max=max(Max,V);
		if(V>Max){
			Max=V;
			for(int i=0;i>n;
	
	int weight[n],value[n];
	
	int path[n]={0};//                
	
	cout<>weight[i]>>value[i]; 
	} 
	cout<>W; 
	int Max=0;
	func(weight,value,W,n,path,Max,0,0,0);
	cout<

분기 한계

#include 
#include 
using namespace std;

int Bound(int* Weights,int* Values,int n,int W,int num,int current_w,int current_v){
	int i=num+1;
	for(;i=n){
			Weight=current_w;
			Profit=current_v;
			i=n;
			for(int i=0;i>n;
	cout<>W; 
	int Weight[n];
	int Value[n];
	int *path; 
	cout<>Weight[i]>>Value[i]; 
	} 
	
	path=fun(Weight,Value,W,n);
	for(int i=0;i