C Абсцисса, вписывающаяся в алгоритм длины

Question

Я не мог найти алгоритм в моей проблеме.

Существуют разные виды размеров абсцисс. Длина в целых числах.

И чем определен размер для создания из абсцисс. Мне нужен алгоритм, который находит лучший способ слить, подогнать, составить абсциссы до определенной длины. (мы в 1D)

Чем меньше строк, тем лучше, и мне нужно найти лучшую комбинацию. Количество каждой предопределенной абсциссы бесконечно.

Наименьшая абсцисса всегда имеет размер 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.

Проблема с рюкзаком

Существует решение DP для ранца в псевдополиномиальном времени