ogey
2021-03-19T13:15:11+00:00
题目要求是输入几个砝码的重量，在天平平衡的前提下最重能放几个砝码。
例:输入 1 3 6 7，最重的的放法就是左边1 6右边放7。
某公司的机考题，当时就总觉得自己好像有点思路，然后就是想不出。 我好菜啊 [s:ac:晕]
做一轮背包然后扫描一遍吧。
重量V是可达的，然后去看重量V/2是不是可达就行了。
早上是docker晚上是acm
这就是周五吗[s:ac:喷]
我第一时间想到的是一个特别笨的办法，就是从大到小，看看哪个数可以拆成两个数的和……
编辑，没有正确理解题意
[quote][pid=503242798,26070351,1]Reply[/pid] Post by [uid=38370144]高高高一直都活在冬天[/uid] (2021-03-26 21:32):
我第一时间想到的是一个特别笨的办法，就是从大到小，看看哪个数可以拆成两个数的和……[/quote]但是会存在比如 1 2 5 6 8这种左边5 6右边1 2 8这种[s:ac:晕]
不可以先找最大的数放，在用这个数来判断已有的其他数
[quote][pid=503243674,26070351,1]Reply[/pid] Post by [uid=35216312]アクセラーコ[/uid] (2021-03-26 21:37):
但是会存在比如 1 2 5 6 8这种左边5 6右边1 2 8这种[s:ac:晕][/quote]奥，是我考虑的少了！
动归
[1,3,6,7]
从左到右依次更新动归数组，数组内放抵达方法。
1：1可达，方法为1
1,3：
1可达，方法为1
3可达，方法为3
4可达，方法为1，3
1，3，6：
1可达，1
3可达，3
4可达，1，3
6可达，6
7可达，1，6
9可达，3，6
10可达，1，3，6
1，3，6，7：
1～1
3～3
4～1，3
6～6
7～1，6
9～3，6
10～1，3，6
7～7
8～1，7
10～3，7
………
然后找不重叠的，比如对于7，有两种不重叠的实现。10也有两种实现但是有重叠
感觉时空复杂度好像都有点大，等大手子们的更好方案[img]http://img.nga.178.com/attachments/mon_201209/14/-47218_5052bc521c04b.png[/img]
[quote][pid=503245121,26070351,1]Reply[/pid] Post by [uid=734189]lyhtsm[/uid] (2021-03-26 21:45):
动归
[1,3,6,7]
从左到右依次更新动归数组，数组内放抵达方法。
1：1可达，方法为1
1,3：
1可达，方法为1
3可达，方法为3<......[/quote]哦忽然看明白了一楼的解法…
14可达，去查7，如果也有就OK
先求和，然后分别减掉其中一个，剩下来的必须是偶数；然后这个偶数除2，看剩下的能否有加起来等于一半的。
想了个递归的 自己随便找了几个例子怎么感觉好像都能凑出来……时间复杂度爆炸 目前没有验证正确性
先给砝码按重量排序 然后求出重量和s 判断是否有砝码大于s/2 如果有 剔除所有大于s/2的砝码 再重新求和s
看你题目是默认int么 那就判断s是否为奇数 奇数必不可能平衡 去掉一个最小的奇数 然后从大往小加砝码凑s/2 如果可以凑到 那就是只剔除一个砝码 如果不行 则剔除一个最小的偶数 然后递归
[quote][pid=503245499,26070351,1]Reply[/pid] Post by [uid=734189]lyhtsm[/uid] (2021-03-26 21:47):
哦忽然看明白了一楼的解法…
14可达，去查7，如果也有就OK[/quote]光这样不行的
比如砝码只有7和14
或者砝码是7，4，10
还需要一些更严密的条件
求和，算出一半的总重
然后组合一下看能不能组成一半总重，能的话就满足
不能的话就找能不能组成一半总重减一，能的话再看剩下的能不能满足
然找不到就一直减
[s:ac:嘲笑1]不需要思路 都什么版本了还最优解？
[quote][pid=503245121,26070351,1]Reply[/pid] Post by [uid=734189]lyhtsm[/uid] (2021-03-26 21:45):
动归
[1,3,6,7]
从左到右依次更新动归数组，数组内放抵达方法。
1：1可达，方法为1
1,3：
1可达，方法为1
3可达，方法为3
4可达，方法为1，3
1，3，6：
1可达，1
3可达，3
4可达，1，3
6可达，6
7可达，1，6
9可达，3，6
10可达，1，3，6
1，3，6，7：
1～1
3～3
4～1，3
6～6
7～1，6
9～3，6
10～1，3，6
7～7
8～1，7
10～3，7
………
然后找不重叠的，比如对于7，有两种不重叠的实现。10也有两种实现但是有重[/quote]老哥你这个可以
我发现我的连最基础的1367都算不出来 难怪觉得正确性无法验证
你这个重叠只需要判断最大相同的两个数组是否包含同一元素就可以了 不过时间复杂度确实爆炸
动态规划，F(i，j)代表前i个砝码在天平差值为j时的左端最大重量
状态转移为枚举I J 在第i个砝码放左边 放右边 不放的情况取最优解
时间复杂度为O(NM) N为砝码数量 M为总重量除二
这就是个背包问题的变种，动态规划可解，占个坑回去写