题意： 题意相当于：给你六种物品，每种物品对应有 \(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; }转载于:https://www.cnblogs.com/Tianwell/p/11414394.html
相关资源：JAVA上百实例源码以及开源项目