题意相当于: 给你六种物品, 每种物品对应有 \(num[i] (i 为物品编号)\) 个, 同时第 \(ith\) 物品价值为 & i&, 现在问你能否将这些物品分成两堆, 使得每堆的价值相同
思路:
我们可以用 dfs 去暴力搜索, 当然这里使用多重背包的想法. 即有 N 个物品 对应每个物品都有对应的 体积, 能否找到任意 \(M\) 个把 体积为 \(tot/2\) (tot 为总价值) 的包装满.
关于装满问题, 我们只需要找到是否存在路径即可. 把 \(dp[0]\) 设为 1, 然后转移, 看是否能达到 \(dp[tot/2]\)
对于多重背包, 我们可以直接转化为 01 背包来做, 同时在利用二进制原理优化 (跟快速幂一样), 把这些物品转化成新的不同物品, 最后跑一次 01 背包即可.
- code:
- #include <bits/stdc++.h>
- #define iOS iOS::sync_with_stdio(0); cin.tie(0);
- #define accept 0
- #define mp make_pair
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int, int> pii;
- const int inf = 0x3f3f3f3f;
- const int maxn = 3e5+7;
- const int maxm = 1e6+7;
- const int mod = 1e9+7;
- int dp[maxn];
- int res[1000];
- int num[7];
- int main(){
- int cas = 0;
- while(~scanf("%d",&num[1])){
- int tot = 0;
- for(int i=2;i<=6;i++){
- scanf("%d",&num[i]);
- }
- for(int i=1;i<=6;i++){
- tot += num[i]*i;
- }
- if(tot==0) break;
- printf("Collection #%d:\n",++cas);
- if(tot%2){
- printf("Can't be divided.\n\n"); // 注意有空行
- continue;
- }
- memset(dp,0,sizeof(dp));
- memset(res,0,sizeof(res));
- int flag = 0;
- tot /= 2;
- int cnt = 1;
- for(int i=1;i<=6;i++){
- int k = 1;
- while(k<num[i]){
- res[cnt++] = k*i;
- num[i] -= k;
- k <<= 1;
- }
- if(num[i]){
- res[cnt++] = num[i] * i;
- }
- }
- dp[0] = 1;
- for(int i = 1;i<cnt;i++){
- for(int j=tot;j>=res[i];j--){
- dp[j] += dp[j-res[i]];
- }
- }
- if(dp[tot]){
- printf("Can be divided.\n\n");
- }
- else{
- printf("Can't be divided.\n\n");
- }
- }
- return accept;
- }
来源: http://www.bubuko.com/infodetail-3171146.html