<分区>
我对我们老师作为作业提出的算法有一点疑问。它是这样的:
有很多这样的棍子:
4(要用的桩数)
11 7 5 4(棍子的长度)
1 1 3 3(每个长度有多少根棍子)
我必须找出一种算法，通过合并它们来形成最少数量的木棍。前面例子的解决方案是这样的:
15 3 (15(最佳总和) * 3(最小支数) = 45 = 11*1 + 7*1 + 5*3 + 4*3)
11 4
7 4 4
5 5 5
现在我不是要你们解决这个问题，而是要给我一条路线，我试图将其减少为“进行更改”问题，直到我必须选择的部分之前它一直很好从剩下的解决方案中选出好的解决方案。
所需的复杂度是指数级的，限制是:
- 0 < 支 < 100
- 0 < max_sum_of_sticks < 1000
那么你们对此有什么想法吗？
非常感谢您的宝贵时间。
关于最小木棍数量的解释:例如，如果我有一组木棍。要形成的总和是 80，我有相当多的解决方案:
1根长80的棍子
2根长40的木棍
4 根长 20 等。
第一个是微不足道的，我们放弃了它，对于其余的解决方案，我必须测试我是否可以用我拥有的棍子组构建它们，因为有可能选择的解决方案，例如 2*40，是这是一个可靠的，因为我们有未使用过的木棍。