POJ 2923 Exponentiation (DP)

2217 단어 동적 기획
제목 유형 DP
제목의 의미
최대 10개의 물품(중량 1-100사이)을 주고 적재량은 각각 C1과 C2의 차 두 대(1<=C1, C2<=100)
이 두 대의 차를 몇 번을 끌고 가야 모든 물품을 가져갈 수 있느냐고 물었다(한 번은 최대한 많은 물품을 두 대의 차에 각각 놓고 가면 물품을 분할할 수 없다)
문제풀이 방법
물품이 10개밖에 없는데 과감하게 폭력적으로 해결하다
우선 상태 압축으로 몇 개 물품의 집합을 하나의 숫자로 압축한다(예를 들어 물품 1은 1에 대응하고 물품 2는 2에 대응하고 물품 3은 4에 대응하면 물품 1과 3으로 구성된 물품 집합에 대응하는 숫자는 5이다
하면, 만약, 만약...
5 & (1<(x-1)))가 0이 아니면 5가 표시하는 집합에 x번째 아이템 포함
그리고 하나의 그룹 dp[i]로 i 이 집합된 물품을 운반하는 데 필요한 최소 횟수를 표시합니다
그러면 어떤 끌어간 물품 집합 j에 대해 이동식 dp[i|j]=min(dp[i|j], dp[i]+1)이 있다.(그중 집합 i와 j는 같은 물품이 없다) (코드와의 이동식은 사실 등가이다)
어떤 집합 j가 한 번에 끌려갈 수 있는지 판단하기 위해 이 집합의 서브집합을 직접 매거한다. 즉, 이 서브집합이 C1에 끌려갈 수 있고 j의 나머지 집합 요소는 C2에 끌려갈 수 있다. 만약에 무게가 부합되면 합법적이고 상세한 코드 참조
코드 참고. - 궁금한 거 있으면 댓글로 남겨주시면 빨리 답장해드릴게요.
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int INF = 1<<30;

int n, c1, c2;
int A[20];
int dp[1100];

bool Judge(int x) { //    x                  
	int B[20], nb = 0, S = 0;
	for( int i=0; i<n; i++ ) if(x & (1<<i)) S += A[i], B[nb++] = i; //     x      
	for( int i=0; i<(1<<nb); i++ ) { //    x        
		int sum = 0;
		for( int j=0; j<nb; j++ ) {
			if(i & (1<<j)) sum += A[B[j]]; // sum     C1          
		}
		if(sum <= c1 && S - sum <= c2) return true; // S - sum     C2         
		if(sum <= c2 && S - sum <= c1) return true;
	}
	return false;
}

int main() {
	//freopen("in", "r", stdin);
	int t, cnt = 1;
	scanf("%d", &t);
	while(t--) {
		scanf("%d%d%d", &n, &c1, &c2);
		for( int i=0; i<n; i++ ) scanf("%d", &A[i]);
		for( int i=0; i<(1<<n); i++ ) dp[i] = INF;
		dp[0] = 0;
		for( int i=0; i<(1<<n); i++ ) { //              i 
			if(Judge(i)) { //       i   
				for( int j=0; j<(1<<n); j++ ) { //      i       j 
					if((j & i) == i) { //    j    i    j   
						if(dp[j] > dp[j^i] + 1) {
							dp[j] = dp[j^i] + 1;
						}
					}
				}
			}
		}
		printf("Scenario #%d:
", cnt++); printf("%d

", dp[(1<<n)-1]); } return 0; }

좋은 웹페이지 즐겨찾기