【 POJ 1014 】 다 중 가방 나 누 기, 이 진 아 이 템 나 누 기 01 가방

직접 01 가방 을 만 들 면 아 이 템 수량 을 누적 하여 20000 아 이 템 의 01 가방 을 만들어 TLE 를 지정 합 니 다. 제 가 말 하지 않 아 도 되 죠?
본 고의 최 적 화 는 이 진 최적화, O (logn) 이다. 완전 가방 기록 에 사 용 된 개수 의 O (n) 알고리즘 에 대해 본 고 는 설명 하지 않 고 블 로그 의 '가방' 분류 에 있다.
바 이 너 리 최적화:
        여러분 은 한 십 진수 가 이 진수 로 바 뀔 수 있다 는 것 을 알 고 있 습 니 다. 그러면 어떤 물품 이 1023 가지, 즉 2 ^ 10 - 1, 이 진 이 111111111 이 라 고 가정 하면 모든 사람 이 (1, 2, 4, 8, 16, 32, 64, 128, 256, 512 곶 개의 물품 을 섞 어 합성 한 큰 물건 으로 볼 수 있 습 니 다. 이 진 수 는 한 사람 당 0 은 바람 직 하지 않다 고 표시 하고 1 은 바람 직 하지 않다 고 표시 합 니 다. 그러면 우 리 는 모든 수 를 다 찾 을 수 있 습 니 다.2 의 정수 멱 - 1 개의 물품 이 아니라면 부족 한 물품 의 개 수 를 보충 하면 된다. 예 를 들 어 1025 는 2 개의 물품 으로 구 성 된 새로운 물품 을 보충 하면 된다.
코드:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;


int n[7],sum;
bool f[121000];

int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k,g;
	int flag;
	for(g=1;;g++)
	{
		flag=sum=0;
		for(i=1;i<=6;i++)
		{
			scanf("%d",&n[i]);
			if(n[i])flag=1,sum+=n[i]*i;
		}
		if(!flag)return 0;
		printf("Collection #%d:
",g); if(sum&1) { printf("Can't be divided.

"); continue; } sum>>=1; memset(f,0,sizeof(f)); f[0]=1; for(i=1;i<=6;i++) { /* */ int temp; for(j=0;(1<<j)<n[i];j++) {/* for (1<<j) , 。*/ n[i]-=(1<<j); temp=(1<<j)*i; for(k=sum-1;k>=0;k--)if(f[k]&&k+temp<=sum)f[k+temp]=1; if(f[sum])break; } if(n[i]) {/* “1025” */ temp=n[i]*i; for(k=sum-1;k>=0;k--) if(f[k]&&k+temp<=sum) f[k+temp]=1; } /**/ if(f[sum])break; } if(f[sum])printf("Can be divided.

"); else printf("Can't be divided.

"); } return 0; }

번역
번역 결과

좋은 웹페이지 즐겨찾기