POJ 2923 Exponentiation (DP)
2217 단어 동적 기획
제목의 의미
최대 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;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
