c - C横坐标拟合长度算法

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

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

并且比定义的尺寸要从横坐标创建。
我需要一种算法，该算法可以找到最佳方式来合并，拟合，将横坐标组合为定义的长度。
（我们处于一维状态）

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

最小横坐标始终为1。因此，始终可以解决该问题。
结合所有可能性并选择最佳方案不是一种选择。

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

最佳答案

上面的问题类似于带有以下参数的背包问题：

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

伪多项式时间内有针对背包的DP解

关于c - C横坐标拟合长度算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20312711/