Почему существует необходимость приблизительного решения для 0-1 ранца, если входные значения высоки?

Question

На Geeks for Geeks Ссылка , упомянуто, что "если входные значения высоки, то решение для 0-1 ранца становится недостижимым, и существует необходимость приблизительного решения".

---

А в приближенном решении, т. Е. Решении FPTAS, значения, соответствующие весам, модифицируются следующим образом: -

k = (maxVal * ε) / n

val '[i] = этаж (val [i] / k)

И затем применяется то же решение на основе DP.

---

Сомневаюсь, что сложность фактического решения на основе ДП с ранцем 0-1 зависит от веса ранца и количества предметов. Это не включает в себя значения, то почему, если значения высоки, то нам нужно приблизительное решение? И делает ли это делает сложность приближенного решения лучше, чем фактическое решение?

Answer 1

Ты прав. Я думаю, что правильное предложение звучит так: «если входные данные весовые коэффициенты высоки, то решение для 0-1 ранца становится неосуществимым, и существует необходимость приблизительного решения».

На мой взгляд, в посте GeeksforGeeks «входные значения» означает «все числа, которые указаны во входных данных»; он включает в себя как веса, так и значения.