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

请教一道简单的算法题

  •  
  •   levelworm · 2020-11-12 12:55:29 +08:00 · 1497 次点击
    这是一个创建于 1232 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目大致上是这样的,两个砝码分别重 a 和 b,a 和 b 不等,放在一块称重量,可以称 a+b 或者 a-b 的货物(假设 a 更大一些)。那么,假设手上有 N 个重量不等的砝码,可以称哪些重量?要求用递归。

    举例:手上有 1, 4, 9 三个砝码,那么可以称 3, 5, 8, 10, 13 五种重量的货物。

    这道题目我倒是做出来了,但是感觉效率很低:

    大致上是两个函数,第二个是真正的递归函数:

    用的是自己写的伪代码,所谓insert()就是把两个砝码能够称的重量塞进一个 set 中(这样就不会有重复了),而 a exclude A 就是集合 a 把 A 元素去除掉之后得到的子集合。

    void generateWeights(set<int> a) {
    		if (a.size() == 2) {
    			insert(X+a1, X-a1);
    		}
    		else {
    			for A in a {
    				generateWeightsHelper(A, a exclude A);
    			}
    		}
    	}
    
    void generateWeightsHelper(int b, set<int> a) {
    	if (a.size() == 1) {
    		insert(b+a, a-b);	// assuming a>b
    	}
    	else {
    		for A in a {
    			generateWeightsHelper(b, a exclude A);
    		}
    	}
    }
    

    然后我自己设想了一个案例,跟着函数走了一遍,发现重复运算的很多,比如说 insert(3, 5)就出现了两次。

    Example: (1, 4, 9, 15)
    
    Step 1 - generateWeightsHelper(1, (4, 9, 15))
    	Step 1.1 - generateWeightsHelper(1, (4, 9))
    		Step 1.1.1 - generateWeightsHelper(1, 9) -> Insert(8, 10)
    		Step 1.1.2 - generateWeightsHelper(1, 4) -> Insert(3, 5)
    	Step 1.2 - generateWeightsHelper(1, (4, 15))
    		Step 1.2.1 - generateWeightsHelper(1, 4) -> Insert(3, 5)
    		Step 1.2.2 - generateWeightsHelper(1, 15) -> Insert(14, 16)
    	Step 1.3 - generateWeightsHelper(1, (9, 15))
    		Step 1.3.1 - generateWeightsHelper(1, 9) -> Insert(8, 10)
    		Step 1.3.1 - generateWeightsHelper(1, 15) -> Insert(14, 16)
    Step 2 - generateWeightsHelper(4, (1, 9, 15))
    	// 略
    Step 3 - generateWeightsHelper(9, (1, 4, 15))
    	// 略
    

    请问有什么办法可以把这些重复的去掉?如果能够有想法就最好了。

    9 条回复    2020-11-12 23:32:03 +08:00
    daozhihun
        1
    daozhihun  
       2020-11-12 14:00:15 +08:00 via iPhone   ❤️ 1
    重复的你可以用一个 map 来记录算过的,以后碰到了算过的直接取出结果 return 避免重复递归
    binux
        2
    binux  
       2020-11-12 14:03:59 +08:00   ❤️ 1
    为什么我不能单独用一个 4 的砝码称重?
    binux
        3
    binux  
       2020-11-12 14:09:52 +08:00   ❤️ 1
    而且不能同时用 3 个砝码,太简单了,列举 combinations 就完了。
    Vegetable
        4
    Vegetable  
       2020-11-12 14:15:31 +08:00   ❤️ 1
    这不是在算重量,而是让你找出砝码所有的不同摆放方式,再分别计算两边的质量差就完了。
    正如 @binux 说的,连用一个都不行,每次都是全员登场。
    Vegetable
        5
    Vegetable  
       2020-11-12 14:18:22 +08:00   ❤️ 1
    由于天平只有两边,所以一边确定,另一边也确定了。
    那么就是列出 N 个砝码时,其中一边分别放 1 、2 、3...N 个(其实放到一半就行)的方案,就是排列组合那一套。
    misdake
        6
    misdake  
       2020-11-12 14:24:36 +08:00   ❤️ 1
    1.
    你看你的代码,你得到的结果似乎是“假设手上有一些重量不等的砝码,使用 2 个砝码来称重(不多不少,必须是 2 个),可以称哪些重量”
    而不是“假设手上有 N 个重量不等的砝码,可以称哪些重量”

    2.
    你碰到的重复计算的来源是:每一次想要扔掉一个元素的时候,都遍历整个集合
    会出现“先扔掉 1 再扔掉 2”和“先扔掉 2 再扔掉 1”的两种调用,但谁先谁后在这道题中无所谓,重复计算了。
    为了避免重复计算,应当舍弃掉这两种情况中的 1 种,如总是要求“扔掉的数字必须必上一次扔掉的数字更大”
    BiteTheDust
        7
    BiteTheDust  
       2020-11-12 14:50:44 +08:00   ❤️ 1
    很基础的背包问题 01 背包稍微变形下就可以了
    levelworm
        8
    levelworm  
    OP
       2020-11-12 22:30:36 +08:00
    @misdake @binux @Vegetable 多谢,我觉得楼上的朋友们说的有道理,应该允许单个或者多于两个砝码称重,虽然题目没说但是常理来看应该允许。我晚上重新写一下。
    levelworm
        9
    levelworm  
    OP
       2020-11-12 23:32:03 +08:00
    @misdake 我又想了一下,如果允许任意数量的砝码,按照上面 @Vegetable 网友的提示,实际上是考摆放,那么我需要区分左右盘,因为只能右盘的砝码重量多过左边,而不能相反(假设货物固定在左边)。

    按照递归的常规思路,首先确认一个最简情况,就是如果只有一个砝码 a,那么就只能放在右边, Ra 。然后,我有(1, 4, 9, 15)四个砝码,假设我已知(1, 4, 9)所有的摆放组合(R1, R4, R9, L1R4, L1R9, L1R49, etc...),那么增加第四个砝码 15 之后,我能做的就是在所有这些组合里头都把 15 往左右放放试试看(去掉左边太重的结果),再加上 1,4,9 放左边,15 放右边这个结果,以及 15 单独放右边的结果,应该就得到所有的组合了。

    不知道我这个思路对头吗?总觉得那么别扭呢。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1146 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 18:35 · PVG 02:35 · LAX 11:35 · JFK 14:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.