C Abscissas fitting in length algorithm

Question

I couldn't find algorithm at my problem.

There are defined different kinds of sizes abscissas. Lengths is in integers.

And than there is defined size to create from abscissas. I need algorithm which finds best way to merge, fit, compose abscissas to defined length. (we are in 1D)

The fewer lines the better, and i need to find the best combination. Number of every predefined abscissa is infinite.

The smallest abscissa is always size of 1. So the problem is always possible to solve. Combine all possibilities and pick the best is not an option.

for example number of abscissas: 5;
types: 321, 215, 111, 9, 1; length: 900; result: 2x321 + 2x111 + 4x9 => 8 abscissas

Answer 1

The above problem is similar to the knapsack problem with following parameters:-

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

There is DP solution for Knapsack in pseudo polynomial time