HDU 1059 Dividing(マルチバックパック)
HDU 1059 Dividing(マルチバックパック)
http://acm.hdu.edu.cn/showproblem.php?pid=1059
タイトル:
現在、num[i](1<=i<=6)個の価値のある1,2,3,4,5,6の6種類の品物がありますが、すべての品物を2つに分けて、この2つの品物の価値の合計を同じにすることができますか?
分析:
まず、すべての品物の価値とsumを求めます.val、sum_valは奇数で、それでは明らかに分けることができません.それではsum_valが偶数の場合、私たちはm=sum_val/2.私はすべての品物の中から品物を取り出すことができるかどうかを見ることができます:“すべて取った品物の総価値==m?”
各物品の数はnum[i]個であるため、本題は多重リュックサックの問題である.
実は多重リュックサックの问题は01リュックサックに変えて解くことができて、しかし効率は高くありません.だからここで私达は<<リュックサック九讲>の中で言及した二進法圧缩の思想によって本題を解决します.
dp[i][j]=xを選択前のi種類の物品を表す、かつ総価値<=jを前提として、すべての選択された物品が達成できる最大の価値を示す.
val[i]*num[i]>=mのものについては、完全リュックサックを一度だけ使えばいいです.
すなわちdp[i][j]=max(dp[i-1][j],dp[i][j-val[i]+val[i])
val[i]*num[i] 1個2個4個…2^(k-1)個およびnum[i]–2^k+1個
i番目のアイテムからなる上記のアイテムの山ごとに01リュックサックを1回作ればよい.
(なぜ上の区分が正確に解けるのか?上のものはnum[i]個のi類のすべての選択可能なものを覆っているからだ)
最終的に求める:dp[n][m]がmに等しいかどうかを見ればよい.
ACコード:
http://acm.hdu.edu.cn/showproblem.php?pid=1059
タイトル:
現在、num[i](1<=i<=6)個の価値のある1,2,3,4,5,6の6種類の品物がありますが、すべての品物を2つに分けて、この2つの品物の価値の合計を同じにすることができますか?
分析:
まず、すべての品物の価値とsumを求めます.val、sum_valは奇数で、それでは明らかに分けることができません.それではsum_valが偶数の場合、私たちはm=sum_val/2.私はすべての品物の中から品物を取り出すことができるかどうかを見ることができます:“すべて取った品物の総価値==m?”
各物品の数はnum[i]個であるため、本題は多重リュックサックの問題である.
実は多重リュックサックの问题は01リュックサックに変えて解くことができて、しかし効率は高くありません.だからここで私达は<<リュックサック九讲>の中で言及した二進法圧缩の思想によって本題を解决します.
dp[i][j]=xを選択前のi種類の物品を表す、かつ総価値<=jを前提として、すべての選択された物品が達成できる最大の価値を示す.
val[i]*num[i]>=mのものについては、完全リュックサックを一度だけ使えばいいです.
すなわちdp[i][j]=max(dp[i-1][j],dp[i][j-val[i]+val[i])
val[i]*num[i]
i番目のアイテムからなる上記のアイテムの山ごとに01リュックサックを1回作ればよい.
(なぜ上の区分が正確に解けるのか?上のものはnum[i]個のi類のすべての選択可能なものを覆っているからだ)
最終的に求める:dp[n][m]がmに等しいかどうかを見ればよい.
ACコード:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20000+5;
int m;//DP
int dp[maxn*5];
int val[]={1,2,3,4,5,6};//
int num[10]; //
// 01
void ZERO_ONE_PACK(int cost,int val)
{
for(int i=m;i>=cost;i--)
dp[i] = max(dp[i], dp[i-cost]+val);
}
//
void COMPLETE_PACK(int cost, int val)
{
for(int i=cost;i<=m;i++)
dp[i] = max(dp[i], dp[i-cost]+val);
}
//
void MULTIPLE_PACK(int cost,int val,int sum)
{
//
if(cost*sum>=m)
{
COMPLETE_PACK(cost,val);
return ;
}
//log(sum) 01
int k=1;
while(k<sum)
{
ZERO_ONE_PACK(cost*k,val*k);
sum -=k;
k=k*2;
}
ZERO_ONE_PACK(sum*cost,sum*val);
}
int main()
{
int kase=0;
while(scanf("%d%d%d%d%d%d",&num[0],&num[1],&num[2],&num[3],&num[4],&num[5])==6)
{
if(num[0]+num[1]+num[2]+num[3]+num[4]+num[5]==0) break;
printf("Collection #%d:
",++kase);
int sum_val=0;
for(int i=0;i<6;i++)
sum_val+= val[i]*num[i];
if(sum_val%2)
{
printf("Can't be divided.
");
continue;
}
m=sum_val/2;//
memset(dp,0,sizeof(dp));
for(int i=0;i<6;i++)
{
MULTIPLE_PACK(val[i],val[i],num[i]);
}
printf("%s
",m==dp[m]?"Can be divided.":"Can't be divided.");
}
return 0;
}