Почему существует необходимость приблизительного решения для 0-1 ранца, если входные значения высоки?
В Geeks for Geeks Link упоминается, что "если входные значения высоки, то решение для 0-1 ранца становится недостижимым, и существует необходимость приблизительного решения".
И в приближенном решении, т.е. решении FPTAS, значения, соответствующие весам, изменяются следующим образом:
k = (maxVal * ε) / n
val '[i] = пол (val[i] / k)
И затем применяется то же решение на основе DP.
Я сомневаюсь, что сложность фактического решения на основе DP с ранцем 0-1 зависит от веса ранца и количества предметов. Это не включает в себя значения, то почему, если значения высоки, то нам нужно приблизительное решение? И делает ли это делает сложность приближенного решения лучше, чем фактическое решение?
1 ответ
Ты прав. Я думаю, что правильное предложение звучит так: "если входные веса высоки, то решение для 0-1 ранца становится неосуществимым, и существует необходимость приблизительного решения".
На мой взгляд, в посте GeeksforGeeks "входные значения" означает "все числа, которые указаны во входных данных"; он включает в себя как вес, так и значения.