一个算法题，请求哪位大佬指教

背包问题，判断一下 sum/2 能不能凑出来

https://leetcode-cn.com/problems/partition-equal-subset-sum/ leetcode 原题

说实话，我觉得背包问题还是有点难理解的，特别是那个动态规划的遍历顺序，我看了一下这题，我是 17 年做的，错题提交了三次，最后应该是看题解抄的

所有数相加后判断奇偶（奇数直接输出 0 ） => 创建长度为 10000 的值全为 false 的数组（ 100 * 100 ） => 然后就是把输入的数记录到数组里（输入为 1 和 5 的情况就是在数组的 1 ，5 ，6 上置 true ，就是枚举数字相加的可能性） => 如果存在 Arr[(sum >> 1) - N] == true 的情况就输出 1

很模糊的记忆这应该是一个 np complete 问题

不会是字节的吧。字节都是 leetcode 原题。。给你一道困难题也太为难了

试着写了一下，递归

https://gist.github.com/milkpuff/b813e0a990cf88b39ca5f69cff248f07

没有什么代码是 phper 用 for 和数组写不出来的，如果有，再加个 if/else

<?php

/* 输入 */
echo "请输入糖的个数： ";
$count = (int) fgets(STDIN);
echo "请输入每颗糖的重量：";
$tmp = fgets(STDIN);
$tmp = explode(' ', $tmp);
$weight_arr = [];
foreach($tmp as $v) {
array_push($weight_arr, (int) $v);
}
if ($count != count($weight_arr)) {
echo "请输入正确的重量\n";
exit();
}

/* 初始化 */
// 给孩子 A 的重量
$weight_a = 0;
// 给孩子 B 的重量
$weight_b = 0;
// 是否可以平分
$status = false;
// 日志，记录给孩子 A 和孩子 B 的分配方案
$log_plan_a = [];
$log_plan_b = [];
// 将输入的重量列表看作一个环，每次指针指向下位，$count/2 次向上取整即可
for ($n = 0; $n < ceil($count/2) /*$count*/; $n++) {
// 将糖果分为 2 个部分，前$i 个给孩子 A ，后$count - $i 个给孩子 B
// 给孩子 A 的
for ($i = 0; $i < $count - 1; $i++) {
// 奇数个中位数对比时也只需要对比一半
if ($n == ceil($count/2) - 1 && $i == ceil(($count - 1)/2)) {
$weight_b = 0;
$log_plan_b = [];
break;
}
$weight_a += $weight_arr[$i];
array_push($log_plan_a, $weight_arr[$i]);
// 给孩子 B 的
for ($j = $i + 1; $j < $count; $j++) {
$weight_b += $weight_arr[$j];
array_push($log_plan_b, $weight_arr[$j]);
}
if ($weight_a == $weight_b) {
$status = true;
echo '可行的分配方案，一个孩子给：' . implode(', ', $log_plan_a) . '。另一个孩子给：' . implode(', ', $log_plan_b) . "\n";
}
$weight_b = 0;
$log_plan_b = [];
}
$tmp = array_shift($weight_arr);
array_push($weight_arr, $tmp);
$weight_a = 0;
$log_plan_a = [];
}
if ($status) {
echo "1\n";
} else {
echo "0\n";
}

应该这么算就可以了
数组（ a ,b ，c ，....，）
那么 a 可能组合是 a
那么 a ，b 可能组合是 a

应该这么算就可以了
数组（ a ,b ，c ，....，）
那么 a 可能组合是 a
那么 a ，b 可能组合是 a ，b ，a+b
然后 a ，b ，c 的可能组合最多 6 种，
一直算下去，每多一个最多翻倍（重复的需要合并）。总计算次数等于所有糖果之和 x 糖果个数。

也就是最多计算次数不超过 1 百万次。

经典动态规划

https://gist.github.com/msg7086/744d4cf2d81b42e27cb73069ecff939d

随便写了一下，结果应该是对的，就是跑太慢了，一个大点的输入就要跑 0.1 秒，leetcode 上妥妥的 TLE 。

犯傻了，Set 不需要分开记录，全合到一起就行了。改成一个 Set 以后就 AC 了。
答案更新在上面了。要看犯傻答案可以去看 Gist 提交记录。

上来就是 NP-hard 是吧

50 层深的二叉树么？

@cpstar 16# 或者构建一个 n 位 bit ，一共 2^n 个权重，然后遍历 sum(ai*(0,1))=weight/2 即可。不就俩熊孩子么。

if (allsum(candies)%2==1) return 0
for (i=0..2^n-1) {
sum=0
for (j=0..n-1) sum+=candies(j)*(i & 2^j)
if (sum==allsum(candies)/2) return 1
}
return 0

先排序，然后双指针，一个从头到尾 一个从尾到头

import random
import time

items = [random.randint(1, 100) for _ in range(100)]

start = time.time()
su = sum(items)
if su & 1:
____print("NO")
else:
____target = sum(items) // 2
____items.sort(reverse=True)
____memo = set()
____for i in items:
________tmp = {i}
________for j in memo:
____________if i + j <= target:
________________tmp.add(i + j)
________if len(memo) < len(tmp):
____________memo = tmp | memo
________else:
____________memo = memo | tmp
____if target in memo:
________print("YES")
____else:
________print("NO")
print(time.time() - start)


python3.10 跑 大约 0.04 秒

01 背包问题，leetcode 416. 分割等和子集，看看题解吧

@msg7086
不用排序和反转吧。。
排序和反转是为了先处理大数处理的快么？

生成函数来解决, n0, n1, n2 ..... nl 如果存在一半的划分, 当且仅当多项式
(1+x^n0)*(1+x^n1)*......*(1+x^nl) 的展开中 x^(sum/2) 的系数不等于 0

写成代码就是

int sum = 0;
for (int i: nums) {
sum += i;
}

if (sum % 2 != 0) {
return false;
}
int[] product = new int[sum + 1];
product[0] = 1;
product[nums[0]] = 1; // 1 + x^num[0]
for (int i=1; i<nums.length; i++) { // product * (1 + x^(nums[i]))
int e = nums[i];
for (int j=product.length - 1; j>=0; j--) {
if (product[j] != 0) {
product[j + e] += product[j];
}
}
}
return product[sum / 2] != 0;

@retanoj 对，感觉会稍微快一点点。跑 leetcode 测试集，1036 ms → 480 ms 。

@msg7086
我觉得这个跟测试集有关 ;(
我考虑的是，如果测试样例是排序不友好的，可能在排序那个地方的耗时会凸显出来

@falsemask 谢谢

@milkpuff 谢谢

@liuxu 谢谢，但是我只会 java 和 c++，这个没学过，不过我看到题解了，谢谢

@msg7086 谢谢

其实转变一下思维，就是要找 是否有 x 个数字的和为总糖果和的一半