V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ha2ha
V2EX  ›  程序员

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

  •  
  •   ha2ha · 2022-02-20 21:37:54 +08:00 · 3644 次点击
    这是一个创建于 998 天前的主题,其中的信息可能已经有所发展或是发生改变。
    • 下面是题目

    妈妈从超市买了 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

    31 条回复    2022-02-21 23:05:49 +08:00
    zxCoder
        1
    zxCoder  
       2022-02-20 21:44:38 +08:00
    背包问题,判断一下 sum/2 能不能凑出来
    falsemask
        2
    falsemask  
       2022-02-20 21:59:31 +08:00
    falsemask
        3
    falsemask  
       2022-02-20 22:01:33 +08:00
    说实话,我觉得背包问题还是有点难理解的,特别是那个动态规划的遍历顺序,我看了一下这题,我是 17 年做的,错题提交了三次,最后应该是看题解抄的
    sweetcola
        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
    anonymousar
        5
    anonymousar  
       2022-02-20 22:43:53 +08:00
    很模糊的记忆这应该是一个 np complete 问题
    quzard
        6
    quzard  
       2022-02-20 22:53:59 +08:00 via Android
    不会是字节的吧。字节都是 leetcode 原题。。给你一道困难题也太为难了
    milkpuff
        7
    milkpuff  
       2022-02-20 23:29:21 +08:00
    liuxu
        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";
    }
    pagxir
        9
    pagxir  
       2022-02-21 00:31:58 +08:00 via Android
    应该这么算就可以了
    数组( a ,b ,c ,....,)
    那么 a 可能组合是 a
    那么 a ,b 可能组合是 a
    pagxir
        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 糖果个数。
    pagxir
        11
    pagxir  
       2022-02-21 00:41:14 +08:00 via Android
    也就是最多计算次数不超过 1 百万次。
    MegrezZhu
        12
    MegrezZhu  
       2022-02-21 04:11:43 +08:00
    经典动态规划
    msg7086
        13
    msg7086  
       2022-02-21 07:11:11 +08:00
    https://gist.github.com/msg7086/744d4cf2d81b42e27cb73069ecff939d

    随便写了一下,结果应该是对的,就是跑太慢了,一个大点的输入就要跑 0.1 秒,leetcode 上妥妥的 TLE 。
    msg7086
        14
    msg7086  
       2022-02-21 07:20:44 +08:00
    犯傻了,Set 不需要分开记录,全合到一起就行了。改成一个 Set 以后就 AC 了。
    答案更新在上面了。要看犯傻答案可以去看 Gist 提交记录。
    vance123
        15
    vance123  
       2022-02-21 08:01:08 +08:00
    上来就是 NP-hard 是吧
    cpstar
        16
    cpstar  
       2022-02-21 08:10:03 +08:00
    50 层深的二叉树么?
    cpstar
        17
    cpstar  
       2022-02-21 08:13:27 +08:00
    @cpstar 16# 或者构建一个 n 位 bit ,一共 2^n 个权重,然后遍历 sum(ai*(0,1))=weight/2 即可。不就俩熊孩子么。
    cpstar
        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
    xipuxiaoyehua
        19
    xipuxiaoyehua  
       2022-02-21 08:45:20 +08:00 via iPhone
    先排序,然后双指针,一个从头到尾 一个从尾到头
    MoYi123
        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 秒
    eh
        21
    eh  
       2022-02-21 10:20:05 +08:00
    01 背包问题,leetcode 416. 分割等和子集,看看题解吧
    retanoj
        22
    retanoj  
       2022-02-21 10:40:23 +08:00
    @msg7086
    不用排序和反转吧。。
    排序和反转是为了先处理大数处理的快么?
    lff0305
        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;
    msg7086
        24
    msg7086  
       2022-02-21 11:04:20 +08:00
    @retanoj 对,感觉会稍微快一点点。跑 leetcode 测试集,1036 ms → 480 ms 。
    retanoj
        25
    retanoj  
       2022-02-21 11:46:35 +08:00
    @msg7086
    我觉得这个跟测试集有关 ;(
    我考虑的是,如果测试样例是排序不友好的,可能在排序那个地方的耗时会凸显出来
    msg7086
        26
    msg7086  
       2022-02-21 12:34:31 +08:00
    @retanoj 数据集最大就 100 个数字,再怎么说也不会很慢的。
    但是算法从大往小跑,找到解的时间比较容易提前。
    ha2ha
        27
    ha2ha  
    OP
       2022-02-21 19:42:02 +08:00
    @falsemask 谢谢
    ha2ha
        28
    ha2ha  
    OP
       2022-02-21 19:42:16 +08:00
    @milkpuff 谢谢
    ha2ha
        29
    ha2ha  
    OP
       2022-02-21 19:43:05 +08:00
    @liuxu 谢谢,但是我只会 java 和 c++,这个没学过,不过我看到题解了,谢谢
    ha2ha
        30
    ha2ha  
    OP
       2022-02-21 19:43:25 +08:00
    @msg7086 谢谢
    theOneMe
        31
    theOneMe  
       2022-02-21 23:05:49 +08:00
    其实转变一下思维,就是要找 是否有 x 个数字的和为总糖果和的一半
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1308 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 18:04 · PVG 02:04 · LAX 10:04 · JFK 13:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.