HDU 1059

1399 단어 최적화 하 다.
제목:http://acm.hdu.edu.cn/showproblem.php?pid=1059
 가방 류 DP.사실 물 로 넘 어 갈 수 있어 요.정 해 는 이 진 최적화 가 필요 하 다. 이 진 최적화 의 원 리 는 쉽게 말 하면... 하나의 수 는 일련의 2 의 배수 나 2 의 배수 에 2 가 아 닌 배수 로 구성 할 수 있다.
다음은 유대 신의 코드 입 니 다.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[20000*8];
int num[7];
int main(){
  int test=0;
  while(scanf("%d",&num[1])!=EOF) {
      ++test; memset(dp,0,sizeof(dp));

      int tot=num[1];
      for(int i=2; i<=6; i++) {
         scanf("%d",&num[i]);
         tot+=num[i]*i;
      } if(!tot) break;

      printf("Collection #%d:
",test); if(tot&1){ printf("Can't be divided.

"); continue; } dp[0]=1; for(int i=1; i<=6; i++) { if(!num[i]) continue; int k,nowv; for(k=1; k<=num[i]; k=k*2) { nowv=k*i; for(int v=tot/2; v>=nowv; v--) if(dp[v-nowv]) dp[v]=1; num[i]-=k; // cout<<k<<endl; } nowv=num[i]*i; // cout<<num[i]<<endl; if(nowv) { for(int v=tot/2; v>=nowv; v--) if(dp[v-nowv]) dp[v]=1; } } dp[tot/2] ? puts("Can be divided.
") : puts("Can't be divided.
"); } return 0; }

좋은 웹페이지 즐겨찾기