妈妈从超市买了 N 颗糖果来分给两个调皮孩子,但是由于糖果是散装的,每颗糖果的重量可能不一样,如果不能恰好将这 N 颗糖果平分(差一丢都不行,且每颗糖果不可拆分),两熊孩子可能会上房揭瓦。为了保护住宅的完整性,请你判断这 N 颗糖果能否平分,只要两个熊孩子所得糖果的重量总和相等,即为平分。
输入格式: 第一行一个正整数 T(T<20),表示样例个数。
随后 T 组案例:
第一行一个整数 N ,(2<=N<=100)
第二行 N 个整数,每个数(1<=ai<=100)表示每颗糖果的重量。
输出格式: 对于每个样例,输出 1 表示可平分,否则输出 0 。
输入样例: 2 6 1 1 1 1 1 5 5 2 6 10 7 3 输出样例: 1 0
1
zxCoder 2022-02-20 21:44:38 +08:00
背包问题,判断一下 sum/2 能不能凑出来
|
2
falsemask 2022-02-20 21:59:31 +08:00
|
3
falsemask 2022-02-20 22:01:33 +08:00
说实话,我觉得背包问题还是有点难理解的,特别是那个动态规划的遍历顺序,我看了一下这题,我是 17 年做的,错题提交了三次,最后应该是看题解抄的
|
4
sweetcola 2022-02-20 22:05:54 +08:00
所有数相加后判断奇偶(奇数直接输出 0 ) => 创建长度为 10000 的值全为 false 的数组( 100 * 100 ) => 然后就是把输入的数记录到数组里(输入为 1 和 5 的情况就是在数组的 1 ,5 ,6 上置 true ,就是枚举数字相加的可能性) => 如果存在 Arr[(sum >> 1) - N] == true 的情况就输出 1
|
5
anonymousar 2022-02-20 22:43:53 +08:00
很模糊的记忆这应该是一个 np complete 问题
|
6
quzard 2022-02-20 22:53:59 +08:00 via Android
不会是字节的吧。字节都是 leetcode 原题。。给你一道困难题也太为难了
|
7
milkpuff 2022-02-20 23:29:21 +08:00
|
8
liuxu 2022-02-20 23:58:38 +08:00 1
没有什么代码是 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"; } |
9
pagxir 2022-02-21 00:31:58 +08:00 via Android
应该这么算就可以了
数组( a ,b ,c ,....,) 那么 a 可能组合是 a 那么 a ,b 可能组合是 a |
10
pagxir 2022-02-21 00:38:57 +08:00 via Android
应该这么算就可以了
数组( a ,b ,c ,....,) 那么 a 可能组合是 a 那么 a ,b 可能组合是 a ,b ,a+b 然后 a ,b ,c 的可能组合最多 6 种, 一直算下去,每多一个最多翻倍(重复的需要合并)。总计算次数等于所有糖果之和 x 糖果个数。 |
11
pagxir 2022-02-21 00:41:14 +08:00 via Android
也就是最多计算次数不超过 1 百万次。
|
12
MegrezZhu 2022-02-21 04:11:43 +08:00
经典动态规划
|
13
msg7086 2022-02-21 07:11:11 +08:00
https://gist.github.com/msg7086/744d4cf2d81b42e27cb73069ecff939d
随便写了一下,结果应该是对的,就是跑太慢了,一个大点的输入就要跑 0.1 秒,leetcode 上妥妥的 TLE 。 |
14
msg7086 2022-02-21 07:20:44 +08:00
犯傻了,Set 不需要分开记录,全合到一起就行了。改成一个 Set 以后就 AC 了。
答案更新在上面了。要看犯傻答案可以去看 Gist 提交记录。 |
15
vance123 2022-02-21 08:01:08 +08:00
上来就是 NP-hard 是吧
|
16
cpstar 2022-02-21 08:10:03 +08:00
50 层深的二叉树么?
|
17
cpstar 2022-02-21 08:13:27 +08:00
@cpstar 16# 或者构建一个 n 位 bit ,一共 2^n 个权重,然后遍历 sum(ai*(0,1))=weight/2 即可。不就俩熊孩子么。
|
18
cpstar 2022-02-21 08:28:21 +08:00
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 |
19
xipuxiaoyehua 2022-02-21 08:45:20 +08:00 via iPhone
先排序,然后双指针,一个从头到尾 一个从尾到头
|
20
MoYi123 2022-02-21 10:10:40 +08:00 1
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 秒 |
21
eh 2022-02-21 10:20:05 +08:00
01 背包问题,leetcode 416. 分割等和子集,看看题解吧
|
23
lff0305 2022-02-21 11:01:04 +08:00
生成函数来解决, 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; |
31
theOneMe 2022-02-21 23:05:49 +08:00
其实转变一下思维,就是要找 是否有 x 个数字的和为总糖果和的一半
|