讨论/面试考题/大佬们帮忙看一道题目。做到头秃/
大佬们帮忙看一道题目。做到头秃

题目

假设有4条小船,有一堆箱子,每个箱子的重量不一定相等,现在要把这些箱子全部装到船上,要求每条船装载后载重是一样的。

请问这些箱子能否按要求装载?

输入为箱子数组,每个元素表示个箱子的重量,输出位是否能按照要求装载这些箱子。

输入

[1,1,2,2,2]

输出

true

说明

能按照要求装载,每条船载重为2

范围

箱子数不超过15, 箱子重量最高可达10e9
展开讨论

抛砖引玉一下,只会状压 dp 后再处理,等大佬更优的解法
dp[i][j] 表示前 i 个箱子中 j 对应的箱子的总重量, 若 jk 位为 1 ,则第 k 个箱子包含在内(实际写出来可以用一维数组即可)
可以在 O(n * (2 ^ n)) 内求出所有情况,然后找到重量等于所有箱子总重量的 1/4 的结果(这样的情况应该不多)
然后 搜索 或者 再次 dp

  • 搜索:对刚刚的结果进行搜索,找 4 个能在一起能恰好用完所有箱子的情况,找到则返回 true ,否则返回 false
  • DP 看起来很简单,就不说了
展开全部 7 讨论