C 横坐标拟合长度算法

Question

我找不到解决我的问题的算法。

定义了不同种类的尺寸横坐标。长度为整数。

然后从横坐标创建定义的大小。我需要找到将横坐标合并、拟合、组合到定义长度的最佳方法的算法。(我们在一维)

行数越少越好，我需要找到最佳组合。每个预定义的横坐标的数量是无限的。

最小的横坐标总是大小1。所以问题总是可以解决的。结合所有可能性并选择最好的不是一个选择。

例如横坐标数量:5；
类型:321、215、111、9、1；长度:900；结果:2x321 + 2x111 + 4x9 => 8 个横坐标

Answer 1

上述问题与背包问题类似，参数如下:-

knapsack capacity = length = 900
items weights : 321 (900/321=2 times), 215 (900/215=4 times), 111(900/111=8 times).....
values = weights

maximize profit & store min needed abscissas of each subproblem


if max profit == knapsack capacity
   solution exists retrace solution with minimum abscissas

else doesnt exist.

Knapsack problem

Knapsack存在伪多项式时间内的DP解