poj 1014 dividing

여기 찍고 원제 1014.
대략 제목: 6가지 가치가 있는데 각각 1-6의 광석이...각각 num[i]개가... 두 사람에게 같은 가치의 광석을 나눌 수 있느냐고 물었다.다중 가방에 2진법 최적화 방법.순수한 dp와 dfs가 더 있을 것 같습니다.
우선 총가치가 0이거나 홀수라면 균등하게 나눌 수 없다는 것이 분명하다.나머지 짝수라면 다중 가방, dp[j]로 j의 돌을 장착할 수 있는 최대 가치를 기록합니다.바이너리 최적화도 있어.

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[1000000];
int n[10],ans=1,i,k,j,sum;
int main()
{
    while(1)
    {
        sum = 0;
        for(i = 1;i <= 6;i ++)
        {
            cin>>n[i];
            sum += n[i]*i;
        }
        if(sum==0) break;
        if(sum % 2 == 1) printf("Collection #%d:
Can't be divided.

",ans);
        else
        {
            memset(dp,0,sizeof(dp));
            sum/= 2;
            for(i = 1;i <= 6;i ++)
            {
                k = 1;
                while(n[i] > k)
                {
                    for(j = sum;j >= k * i;j --)
                        dp[j] = max(dp[j],dp[j-k*i] + k*i);
                    n[i] -= k;
                    k *= 2;
                }
                for(j = sum;j >= n[i] * i;j --)
                    dp[j] = max(dp[j],dp[j-n[i]*i] + n[i] * i);
            }
            if(dp[sum] == sum)
                printf("Collection #%d:
Can be divided.

",ans);
            else
                printf("Collection #%d:
Can't be divided.

",ans);
        }
        ans ++;
    }
    return 0;
}