알고리즘 노트 8 DFS
1476 단어 알고리즘 노트
사고방식은 모든 물품에 두 가지 방법이 있는데 선택하거나 선택하지 않는 것은 미로의 갈림길, 귀속 중의 귀속식에 해당한다.그러나 물품의 총 무게가 가방 용량 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개의 수를 매거하는 모든 방안과 같다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
leetcode 스크립트 일기의 검증 두 갈래 검색 트리두 갈래 나무를 정해 효과적인 두 갈래 검색 나무인지 아닌지를 판단한다. 두 갈래 검색 트리에는 다음과 같은 정의가 있습니다. 예 1: 두 갈래 나무[2,1,3],true로 돌아갑니다. 예 2: 두 갈래 나무[1,2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
