알고리즘 노트 8 DFS

1.N개 아이템이 있고, 각 아이템마다 무게와 가격이 있으며, 가방 용량 V를 초과하지 않는 상황에서 가격의 합을 최대로 선택하여 최대가치maxValue를 구합니다.
사고방식은 모든 물품에 두 가지 방법이 있는데 선택하거나 선택하지 않는 것은 미로의 갈림길, 귀속 중의 귀속식에 해당한다.그러나 물품의 총 무게가 가방 용량 V를 초과하면 미로 속의 막다른 골목에 해당하고 귀속 중의 귀속 경계에 해당한다.모든 선택 방안을 일일이 열거함으로써 가장 좋은 결과를 얻다.여기서 DFS는 일반 해제, DFSbetter는 가지치기 기교의 최적화를 사용했습니다.

#include 

using namespace std;
const int maxn = 30; 

int n,V,maxValue = 0;
int w[maxn],c[maxn];

//index ,sumW,sumC  
void DFS(int index, int sumW, int sumC){
	
	if(index == n){		// n ,  
		if( sumW <= V && sumC > maxValue){
			maxValue = sumC;			
		}
		return ;
	}
 	
 	// ,  
	DFS( index+1, sumW, sumC);		// index ,index(0~n-1); 
	DFS( index+1, sumW+w[index], sumC+c[index]);		// index ,  
} 

//  
void DFS_better(int index ,int sumW, int sumC){
	
	if(index == n) return;
	
	DFS(index+1, sumW,sumC);
	
	if(sumW + w[index] <= V){		// index  
		if(sumC +c[index] > maxValue){
			maxValue = sumC + c[index];
		}
		DFS(index+1, sumW + w[index],sumC + c[index]);
	}

} 
int main(){
	
	scanf("%d%d", &n,&V);
	
	for(int i=0; i

이것은 일련의 DFS 문제 해결 방법, 즉 이 서열의 모든 하위 서열을 열거하는 서열을 정하는 데 적용된다(연속하지 않을 수 있다).예를 들어 서열\1,2,3)의 모든 하위 서열은\I}, {2}, {3), {1,2}, {1,3},{2,3), {1,2,3). 모든 서열을 매거하는 목적은 명백하다. 그 중에서'최우수'서열을 선택하여 모든 서열에서 가장 우수하다는 특징을 가지게 할 수 있다. 필요하다면 이 최우수 서열을 저장할 수도 있다. 분명히 이 문제는 N개의 정수에서 K개의 수를 매거하는 모든 방안과 같다.