알고리즘 디자인 과 분석 제4 장 동적 계획 (1) [가방 문제]
34803 단어 알고리즘 설계 및 분석
기본 사상: 동적 계획 알고리즘 은 분 치 법 과 유사 하 다. 그 기본 사상 도 해결 해 야 할 문 제 를 몇 개의 키 문제 로 분해 하지만 분 해 를 통 해 얻 은 서브 문 제 는 서로 독립 된 것 이 아니다.서로 다른 하위 문제 의 수 는 항상 다항식 급 만 있다.분 치 법 으로 해 를 구 할 때, 어떤 문 제 는 여러 차례 중복 계산 되 었 다.해 결 된 하위 문제 의 답 을 저장 하고 필요 할 때 구 한 답 을 찾 으 면 중복 계산 을 피하 고 여러 가지 시간 알고리즘 을 얻 을 수 있다.
기본 요소:
1. 최 우수 서브 구조 적 문제 의 최 적 화 는 그 서브 문제 의 최 적 화 를 포함한다.이런 성질 을 최 우선 자 구조 성질 이 라 고 한다.문제 의 가장 좋 은 서브 구조 적 성질 을 분석 할 때 사용 하 는 방법 은 보편성 을 가진다. 먼저 문제 의 가장 좋 은 해석 으로 도 출 된 서브 문제 의 해석 이 가장 좋 은 것 이 아니 라 고 가정 한 다음 에 이 가설 에서 원래 의 문제 보다 가장 좋 은 해석 을 구 조 했 고 창 방 패 를 만 들 수 있다 는 것 을 설명 한다.문제 의 최 우선 서브 구조 성질 을 이용 하여 밑 에서 위로 돌아 가 는 방식 으로 서브 문제 의 최 우선 에서 점차적으로 전체 문제 의 최 우선 을 구성한다.가장 좋 은 서브 구 조 는 문 제 를 동적 계획 알고리즘 으로 풀 수 있 는 전제 이다.
2. 중첩 서브 문제 의 성질 재 귀 알고리즘 이 문 제 를 풀 때 매번 발생 하 는 서브 문 제 는 항상 새로운 문제 가 아니 라 일부 서브 문 제 는 여러 번 반복 적 으로 계산 된다.이런 성질 을 자 문제 의 중첩 성 이 라 고 한다.동적 계획 알고리즘 은 모든 하위 문 제 를 한 번 만 풀 고 한 표 에 저장 합 니 다. 이 문 제 를 다시 풀 어야 할 때 상수 시간 으로 결 과 를 간단하게 볼 수 있 습 니 다.일반적으로 서로 다른 하위 문제 의 개 수 는 문제 의 크기 에 따라 다항식 으로 증가한다.따라서 동적 기획 알고리즘 을 사용 하면 여러 가지 시간 만 있 으 면 비교적 높 은 문제 풀이 효율 을 얻 을 수 있다.
3. 비망록 방법 비망록 방법의 통제 구 조 는 직접 재 귀 방법의 통제 구조 와 같 고 비망록 방법 은 모든 해 제 된 서브 문제 에 비망록 을 만들어 필요 할 때 조회 하고 같은 서브 문제 의 중복 구 해 를 피 하 는 것 과 구별 된다.
기본 절차: 1. 가장 좋 은 성질 을 찾아내 고 그 구조 적 특징 을 묘사한다.2. 최 적 치 를 재 귀적 으로 정의 한다.3. 아래 에서 위로 가장 좋 은 값 을 계산한다.4. 최 우수 치 를 계산 할 때 얻 은 정보 에 따라 구조 가 가장 좋다.
3.1 가방 문제 (문제 분석 은 HTML Help)
가방 문제 (Knapsack problem) 는 조합 이 최 적 화 된 NP 완전 문제 다.
1.01 가방 문제
N 개의 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 아 이 템 의 무 게 는 wi [i] 이 고 가 치 는 val [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 무 게 를 합계 하여 가방 용량 을 초과 하지 않 고 가치 총화 가 가장 큽 니까?
가장 기본 적 인 가방 문 제 는 각 아 이 템 이 하나 밖 에 없어 놓 거나 놓 지 않 는 것 이 특징 이다.
하위 문제 로 상 태 를 정의 합 니 다: 즉 DP [i] [v] 는 앞의 i 개 아 이 템 을 v 용량 의 가방 에 넣 으 면 얻 을 수 있 는 최대 가 치 를 표시 합 니 다.그 상태 전이 방정식 은:
DP[i][v]=max{ DP[i-1][v], DP[i-1][v-wi[i]]+val[i] }。
(공간 압축 가능, DP [v] = max {DP [v], DP [v - wi [i]]] + val [i]})
방정식 은 "앞의 i 개 아 이 템 을 v 용량 의 가방 에 넣 는 것" 이 라 고 설명 했다. 이 문 제 는 i 개 아 이 템 의 전략 (넣 거나 놓 지 않 음) 만 을 고려 하면 앞의 i - 1 개 아 이 템 과 관련 된 문제 로 바 뀔 수 있다. 만약 에 i 개 아 이 템 을 넣 지 않 으 면 문 제 는 '앞의 i - 1 개 아 이 템 을 v 용량 의 가방 에 넣 는 것' 으로 바 뀌 고 가 치 는 DP [i - 1] [v] 이다.i 번 째 아 이 템 을 넣 으 면 문 제 는 '앞의 i - 1 아 이 템 을 남 은 용량 의 v - wi [i] 가방 에 넣 기' 로 바 뀌 는데 이때 얻 을 수 있 는 가장 큰 가 치 는 DP [i - 1] [v - wi] 인 데다 가 i 번 째 아 이 템 을 넣 어 얻 을 수 있 는 가치 val [i] 이다.
공간 복잡 도 최적화
DP [i] [v] 는 DP [i - 1] [v] 와 DP [i - 1] [v - wi [i] 두 가지 문제 가 밀 려 왔 습 니 다. DP [i] [v] 를 밀 때 (즉, 첫 번 째 메 인 순환 에서 DP [v] 를 밀 때) DP [i - 1] [v] 와 DP [i - 1] [v - wi]] 의 값 을 얻 을 수 있 습 니까?사실, 이것 은 매번 메 인 순환 에서 우 리 는 v = V... 0 의 순서 로 DP [v] 를 밀어 야 DP [v] 를 밀 때 DP [v - wi] 가 상태 DP [i - 1] [v - wi] 의 값 을 저장 할 수 있 습 니 다.의사 코드 는 다음 과 같 습 니 다: for i = 1... N for v = V... 0 DP [v] = max {DP [v], DP [v - wi [i]]] + val [i]};
알고리즘 복잡 도: 시간 복잡 도: O (VN), 압축 공간 후 공간 복잡 도 O (V)
코드:
#include
");
}
return 0;
}
2. 완전 가방 은 N 가지 아 이 템 과 V 용량 의 가방 이 있 으 며, 모든 아 이 템 은 무한 정 사용 가능 합 니 다.제 i 종 물품 의 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 비용 을 합 쳐 가방 용량 을 초과 하지 않 고 가치 가 가장 큰 지 알 아 보 세 요.
1 차원 배열, 위조 코드 사용: for i = 1... N for v = 0... V DP [v] = max {DP [v], DP [v - cost] + weight}
분석: 01 가방 의 위조 코드 와 v 의 순환 순서 만 다르다.01 가방 에서 v = V... 0 의 역순 으로 순환 하 는 것 은 i 차 순환 중의 상태 DP [i] [v] 가 상태 DP [i - 1] [v - val [i]] 에서 전달 되 기 때 문 입 니 다.다시 말 하면 이것 은 모든 아 이 템 을 한 번 만 선택 할 수 있 도록 하기 위해 서 이다. 'i 번 째 아 이 템 선택' 전략 을 고려 할 때 i 번 째 아 이 템 에 선택 한 하위 결과 DP [i - 1] [v - wi [i]] 를 근거 로 한다.현재 완전 가방 의 특징 은 바로 모든 아 이 템 이 무한 개 를 선택 할 수 있 기 때문에 'i 번 째 아 이 템 추가 선택' 이라는 전략 을 고려 할 때 i 번 째 아 이 템 에 선 택 된 하위 결과 DP [i] [v - wi [i]] 가 필요 하기 때문에 v = 0... V 의 순서 로 순환 해 야 합 니 다.
[hdu 1114] 코드:
#include
");*/
if(dp[v]==INF)
{
printf("This is impossible.
");
}
else
{
printf("The minimum amount of money in the piggy-bank is %d.
",dp[v]);
}
}
return 0;
}
3. 다 중 가방 문제
N 가지 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 종 아 이 템 은 최대 n [i] 개 를 사용 할 수 있 습 니 다. 모든 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 비용 을 합 쳐 가방 용량 을 초과 하지 않 고 가치 가 가장 큰 지 알 아 보 세 요.
01 가방 으로 전환 가능 구 해: 제 i 종 아 이 템 을 n [i] 건 01 가방 중의 아 이 템 으로 교환 하면 아 이 템 수 를 획득Σn [i] 의 01 가방 문 제 를 직접 해결 하고 복잡 도 는 여전히 O (V *Σn[i])。
방법: i 번 째 물품 을 여러 가지 물품 으로 나 누 는데 그 중에서 모든 물품 은 하나의 계수 가 있 는데 이 물품 의 비용 과 가 치 는 모두 원래 의 비용 과 가 치 를 이 계수 에 곱 한다.이러한 계 수 를 각각 1, 2, 4,..., 2 (k - 1), n [i] - 2k + 1 로 하고 k 는 n [i] - 2 ^ k + 1 > 0 을 만족 시 키 는 최대 정수 이다.예 를 들 어 n [i] 가 13 이면 이 물건 을 계수 로 나 누 어 각각 1, 2, 4, 6 의 네 가지 물건 으로 나눈다.
알고리즘 복잡 도: i 종 아 이 템 을 O (log n [i]) 종 아 이 템 으로 나 누 어 원래 의 문 제 를 복잡 도로 O (V * 로 전환시킨다.Σ질문코드:
#include
",dp[n]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
디 제 스 트 라 알고리즘 으로 권한 부여 그림 의 가장 짧 은 경 로 를 구하 십시오.Description 디 제 스 트 라 알고리즘 으로 나머지 모든 노드 의 가장 짧 은 경 로 를 구하 세 요. Input 먼저 100 보다 작은 정수 n 을 입력 한 다음 에 그림 의 인접 행렬 (10000 은 무...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
