关于google/Amazon高频巧克力甜度follow-up的问题

现在的二分解都是建立在split array顺序是按原先顺序，如果顺序可以是任意的该怎么解呢，典型的情景就是衍变的分工问题，有n项工作的array，数字代表完成的天数，k个工人，一个工作只能由一个工人完成，如何划分工作使最小化工作量最大的工人(另一种问法是如何分配工作使完成的天数最小），minimize max问题，显然工作分配顺序无需有序，可以是任意顺序，看到之前有人说二分工作量排序two pointer取法，但是仔细想想其实是错的，随便举个反例[1,5,6,10,25,28,30],k=3,显然答案是35，但是two point 不会work,除了暴力搜索，还有其他解法吗，大家来集思广益啊- -

0-1 背包了解一下

337845818 发表于 2019-10-25 11:01
0-1 背包了解一下

能给个dp递推式子吗

hackersplendid 发表于 2019-10-25 11:38
能给个dp递推式子吗

这还有啥递推公式啊
https://en.wikipedia.org/wiki/Partition_problem

337845818 发表于 2019-10-26 00:59
这还有啥递推公式啊
https://en.wikipedia.org/wiki/Partition_problem

狭义的0-1背包只能解决2-way。你给的wiki里有一个论文引用，k-way的DP看得晕。