Dividing HDU - 1059 （多重背包）

本文主要是介绍Dividing HDU - 1059 （多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Dividing

 题目链接：HDU - 1059 

题意：一共六种大理石，已知每种大理石的价值(第i种大理石的价值就是i)和数量，问能否将大理石均分成两份价值相同的？注：大理石不能切割，只能整块分配；

思路：如果大理石总价值为奇数，则一定无法分配，如果是偶数就按多重背包分配，分能否分成价值相同的两份；

#include <bits/stdc++.h>
using namespace std;
int dp[500000], cnt[10];
int main(){int cas=0;while(1){int flag=1;int sum=0;for(int i=1; i<=6; i++){scanf("%d", &cnt[i]);if(cnt[i]) flag=0;sum+=cnt[i]*i;}if(flag) break;memset(dp, 0, sizeof(dp));printf("Collection #%d:\n", ++cas);if(sum%2){printf("Can't be divided.\n");}else{sum/=2;for(int i=1; i<=6; i++){if(sum<=i*cnt[i]){for(int j=i; j<=sum; j++){dp[j]=max(dp[j], dp[j-i]+i);}}else{int k=1;while(k<=cnt[i]){for(int j=sum; j>=k*i; j--){dp[j]=max(dp[j], dp[j-k*i]+k*i);}cnt[i]-=k;k<<=1;}for(int j=sum; j>=i*cnt[i]; j--){dp[j]=max(dp[j], dp[j-i*cnt[i]]+i*cnt[i]);}}}if(dp[sum]==sum) printf("Can be divided.\n");else printf("Can't be divided.\n");}printf("\n");}return 0;
}

 

这篇关于Dividing HDU - 1059 （多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---