알고리즘 제5 장 작업

역 추적 알고리즘 에 대한 당신 의 이해
역 추적 법 은 우수한 검색 법 을 선택 하여 우수한 조건 에 따라 앞으로 검색 하여 목 표를 달성 하 는 것 이다.그러나 어떤 단 계 를 탐색 할 때 원래 의 선택 이 좋 지 않 거나 목 표를 달성 하지 못 하면 한 걸음 뒤로 물 러 나 다시 선택 하 는 것 을 발견 했다. 이런 통 하지 않 으 면 되 돌아 가 는 기술 은 역 추적 법 이다.
　　　　
"부분 집합 과" 문제 의 공간 구조 와 제약 함 수 를 설명 하 십시오.
　　　　　　　
집합 S = {x1, x2,..., xn} 은 정수 집합 입 니 다. c 는 정수 입 니 다. 부분 집합 과 문 제 는 S 의 키 집합 S1 이 존재 하 는 지 여 부 를 판단 하여 S1 중의 요 소 를 c 로 합 칩 니 다.부분 집합 과 문 제 를 푸 는 역 추적 법 을 시험 적 으로 설계 하 다.
입력 형식:
입력 데이터 의 첫 번 째 줄 에는 2 개의 정수 n 과 c 가 있 고 n 은 S 의 크기 를 나타 내 며 c 는 부분 집합 과 목표 값 입 니 다.다음 줄 에는 n 개의 정수 가 있 는데 집합 S 의 요 소 를 나타 낸다.부분 집합 과 목표 값 입 니 다.다음 줄 에는 n 개의 정수 가 있 는데 집합 S 의 요 소 를 나타 낸다.
출력 형식:
출력 부분 집합 과 문제 의 해 는 빈 칸 으로 구분 되 고 마지막 출력 뒤에 빈 칸 이 있 습 니 다.문제 가 풀 리 지 않 을 때 "No Solution!" 을 출력 합 니 다.
입력 예시:
여기에 입력 그룹 을 드 립 니 다.예 를 들 면:
5 10
2 2 6 5 4

출력 예시:
여기에 상응하는 출력 을 드 리 겠 습 니 다.예 를 들 면:
2 2 6 

#include
using namespace std;
int  n, c, a[6021], add[6021],sum = 0;
bool x[6021], b;
void backtrack(int t) {
 if (t > n) return;
 if (b == true) return;
 if (sum == c) {
  b = true;
  for (int i = 0; i < n; i++) {
   if (x[i] == true) cout << a[i] << " ";
  }
  return;
 }
 else {
  if (sum + a[t] <= c&&sum+add[t]>=c) {
   sum += a[t];
   x[t] = true;
   backtrack(t + 1);
   x[t] = false;
   sum -= a[t];
  }
  backtrack(t + 1);
 }
 return;
}
int main() {
 cin >> n >> c;
 for (int i = 0; i < n; i++) {
  cin >> a[i]; add[i] += a[i];
 }
   
 for (int j = n - 2; j >= 0; j--) {
  add[j] += add[j + 1];
 }
 backtrack(0);
 if (b == false) cout << "No Solution!";
 system("pause");
 return 0;
}





해 공간 구조: 집합 S 중성자 집합 S1 의 합 은 c 이다.
제약 함수: 현재 의 합 이 c 보다 크 면 잘라 서 되 돌려 줍 니 다.　　　　
　　　
본 장 학습 과정 에서 발생 한 문제 와 프로 그래 밍 의 상황 을 설명해 주 십시오.
가지치기 에 익숙 하지 않 아 버그 가 생 길 수 있 습 니 다.
문제 풀이 노트 (3) - 난수 선택
zoj 1652

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage