hdu 1059 Dividing（多重リュックサック詳細）

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=1059
品質iのものはa[i]個がありますが、2つに分けて品質が同じかどうかは分かりません。品質と奇数は明らかにできません。偶数の時はsum/2のリュックサックを達成すればいいです。残りの自然はsum/2のリュックサックを構成しています。
多重リュックサック:

#include 
#include 
#include 
#include 
using namespace std;
const int maxn=200005;
int a[7],dp[maxn];

int main(){
    int cnt=0;
    while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]){
        memset(dp,0,sizeof(dp));
        cnt++;
        int sum=0;
        for(int i=1;i<=6;i++)
            sum+=a[i]*i;
        if(sum==0)
            break;
        if(sum%2==1){
            printf("Collection #%d:
Can't be divided.
",cnt);
            continue;
        }
        sum/=2;
        for(int i=1;i<=6;i++)
            for(int j=1;j<=a[i];j++)
                for(int k=sum;k>=i;k--)
                    dp[k]=max(dp[k],dp[k-i]+i);
        if(dp[sum]==sum)
            printf("Collection #%d:
Can be divided.
",cnt);
        else
            printf("Collection #%d:
Can't be divided.
",cnt);
    }
    return 0;
}

は明らかにタイムアウトしました。多重リュックサックは多くの01個のリュックサックに分けられましたが、バイナリで分けることができます。このようにいくつかのものが必要です。例えば13を1、2、4、6に分けて、5個必要なら1、4を取ればいいです。

#include
using namespace std;
const int maxn=200005;
int a[7],dp[maxn],w[maxn];

int main(){
    int cnt=0;
    while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]){
        memset(dp,0,sizeof(dp));
        memset(w,0,sizeof(w));
        cnt++;
        int sum=0;
        for(int i=1;i<=6;i++)
            sum+=a[i]*i;
        if(sum==0)
            break;
        if(sum%2==1){
            printf("Collection #%d:
Can't be divided.

",cnt);
            continue;
        }
        sum/=2;
        int cnt0=1;
        for(int i=1;i<=6;i++){
            for(int j=1;j<=a[i];j<<=1){
                w[cnt0++]=j*i;
                a[i]-=j;
            }
            if(a[i]>0)  //           
                w[cnt0++]=a[i]*i;
        }
        for(int i=1;i<=cnt0;i++)
        for(int j=sum;j>=w[i];j--)
            dp[j]=max(dp[j-w[i]]+w[i],dp[j]);
        if(dp[sum]==sum)
            printf("Collection #%d:
Can be divided.

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

",cnt);
    }
    return 0;
}

しかし、このようなpoj 2392と同じやり方は一番速くて、一つの中に入れて、数量と価値の条件の下で、少しずつ加えて、最大の高さに達することができます。

#include
using namespace std;
const int maxn=200005;
int a[7],f[maxn],num[maxn];

int main(){
    int cnt=0;
    while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]){
        memset(f,0,sizeof(f));
        memset(num,0,sizeof(num));
        cnt++;
        int sum=0,ans=0;;
        for(int i=1;i<=6;i++)
            sum+=a[i]*i;
        if(sum==0) break;
        if(sum%2==1){
            printf("Collection #%d:
Can't be divided.

",cnt);
            continue;
        }
        sum/=2;
        f[0]=1;
        for(int i=1;i<=6;i++){
            memset(num,0,sizeof(num));
            for(int j=i;j<=sum;j++)
            if(!f[j]&&f[j-i]&&num[j-i]+1<=a[i]){
                f[j]=1;
                num[j]=num[j-i]+1;
                ans=max(ans,j);
            }
        }
        if(ans==sum)
            printf("Collection #%d:
Can be divided.

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

",cnt);
    }
    return 0;
}