题目

有价值分别为1，2，3，4，5，6 的大理石各 a[1] ，a[2] ，a[3] ，a[4] ，a[5] ，a[6] 块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。其中大理石的总数不超过20000。

输入格式

输入包含多组数据 每组数据占一行，包含6个整数，表示a[1] 至 a[6] 数量 当输入为0 0 0 0 0 0时表示输入结束，且该行无需考虑

输出格式

每组数据输出一个结果，每个结果占一行。 如果可以实现则输出“Can”，否则输出“Can’t”

输入样例

4 7 4 5 9 1 9 8 1 7 2 4 6 6 8 5 9 2 1 6 6 1 0 7 5 9 3 8 8 4 0 0 0 0 0 0

输出样例

Can’t> Can

Can’t Can’t Can

解题思路

前提：💥**明显已知它是多重背包问题 [ 网上告诉我的🦄 ]，所以用二进制优化为01背包问题**，加快求解

正常的背包问题
给一个容量为 wight 的背包，求解装最大的价值

本题为了接近背包

     1. 便于理解，给题目的大理石多个**变量重量，**让重量等于价值，都等于 **i**
     1. 那么题意求解就变成了，能否用**容量****为****总重量一半****的背包装下****最大价值****为****总价值一半****的****物品**
        - 问题1：为什么？
        - **解释 : **题目让求**能否分成两堆价值一样**的大理石
           - 不就是问我用背包能不能装出总价值一半的东西吗 ？
           - 背包装总价值一半的时候背包**容量**正好等于总重量的一半              [ **重量等于价值** ]
        - 问题2：为什么容量为一半的背包装的**最大价值**一定为总价值的一半 ？
        - **解释 : **题目中所有大理石品种的单价都是1，1单位重量等于1单位价值  [ **重量等于价值** ]
           - 所以价值最大就是容量装满，背包容量大小又等于**总价值的一半**
     3. 添加变量重量的好处就是状态转移方程会和普通背包问题的状态转移方程一致

注意**

1. 总价值和必须是偶数，这样才能分成两堆价值一样
2. v [ i ] 即是价值也是重量
3. 状态转移方程
   • **F[m]=max(F[m-wight[i]]+Value[i],F[m])**
   • 本文wight[i]=value[i]

     解题代码

     ```cpp /*

• 参数解释：
• N常量 : 基于大理石品种数量为6
• MAXN变量 : 其值基于题目数量不超过20000,怕20000个都是重量、价值为6的大理石
• sum变量 : 用于统计总价值，其值也等于大理石的总重量
• num数组 : 用于存放大理石的数量
• dp数组 : 用于存储状态表 **/

/**

• 思路解释：
• 【多重背包通过二进制转化变成01背包求解】
• 1.切记切记!!价值和重量均为 i ，二者相同
• 2.本题是给题目多个变量重量，让重量等于价值，这样题目就会变成
• —能否用总重量一半为容量的背包 装下最大价值为 总价值一半的物品 **/

include

include

include

include

include

include

define N 6

using namespace std; const int MAXN = 120005; int sum,num[N],dp[MAXN]; vector v; int main(void) { int sum; while (1) { v.clear(); memset(dp, 0, sizeof(dp)); sum = 0; for (int i = 1; i <= N; i++) { cin >> num[i];//录入 数量 sum += i num[i];//计算总价值 for (int j = 1; j <= num[i]; j <<= 1) { v.push_back(j i);//既是价值也是重量 num[i] -= j;//更新剩余部分 } if (num[i]) { v.push_back(i * num[i]);//二进制剩余部分存储【既是价值也是重量】 } } if (sum) {//全0也可以分配，并且游戏结束了 cout << “ Can “ << endl; return 0; } if (sum % 2) {//总价值奇数，不行 cout << “ Can’t “ << endl; continue; } //已经转化为01背包 int mid = sum / 2; for (int i = 0; i < v.size(); i++) {//i代表物品个数 for (int j = mid; j >= 0; j—) {//j代表容量 if (j >= v[i]) {//v[i]重量，能放进去，考虑i放不放 dp[j] = max(dp[j], dp[j - v[i]] + v[i]); //减去的是weight，加上的是value，由于重量和价值相同故而用一个v[i]表示，含义是不同的 } else {//放不进去 dp[j] = dp[j] ? dp[j] : 0; } } } if (dp[mid] == mid) cout << “ Can “ <<endl; else cout << “ Can’t “<<endl; } return 0; }

<a name="UCSoU"></a>
## 另解代码
```cpp
/***
*    参数解释：
*        Max常量 : 当前状态表的最大价值
*        sum变量 : 用于统计总价值，其值也等于大理石的总重量
*         v数组 : 用于存放二进制优化后大理石的价值 
*          f数组 : 用于存储状态表
****/
for (int i = 0; i < v.size(); i++) {//此时已经转化01背包
    Max += v[i]; 
    Max = min(Max, sum);//无意义语句,max  不超sum
    for (int j = Max; j >= v[i]; j--)
        f[j] |= f[j - v[i]];//灵魂一句，这状态转移方程啥意思？
}