poj 2923dp 상태 압축 + 백팩(화물차 2대 운반)
사고방식: 먼저 n개의 화물에 대해 어떤 조합이 한 번에 운송될 수 있는지 테스트하고 상태 압축을 통해 한다.결과는 s수 그룹에 저장됩니다.이후 가방을 진행하면 한 상태state가 1위로 해당 화물을 선택한 것을 나타낸다.dp[state]는 state가 표시하는 화물 조합을 운송하는 데 필요한 최소 운송 횟수를 나타낸다.디테일 코드
#include <stdio.h>
#include <string.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define INF 0x3fffffff
#define N 1100
int dp[N],s[N],w[N];
int T,n,a,b,m,c=1;
int test(int x){
int i,j,used[1100],sum=0;
memset(used,0,sizeof(used));
used[0] = 1;
for(i = 0;i<n;i++)
if(x & (1<<i)){
sum += w[i];//sum
for(j = a-w[i];j>=0;j--)
if(used[j])
used[j+w[i]] = 1;
}
for(i = a;i>=0;i--)//used[i] 1 i a ，
if(used[i]){
if(sum-i<=b)
return 1;
return 0;
}
}
int main(){
freopen("a.txt","r",stdin);
scanf("%d",&T);
while(T--){
int i,j,top = 0;
scanf("%d %d %d",&n,&a,&b);
m = (1<<n)-1;//
for(i = 1;i<=m;i++)
dp[i] = INF;
dp[0] = 0;
for(i = 0;i<n;i++)
scanf("%d",&w[i]);
for(i = 1;i<=m;i++)//
if(test(i))
s[top++] = i;
for(i = 0;i<top;i++)
for(j = m-s[i];j>=0;j--)
if(!(s[i]&j))//
dp[s[i]|j] = min(dp[s[i]|j],dp[j]+1);
printf("Scenario #%d:
%d
",c++,dp[m]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
