0-1 рюкзак без повторения

Question

Мой вопрос, поэтому O (NW) в задаче knaxackack является псевдо- полиномиальный.

Я читаю много объяснения в Stackoverflow, но я не понимаю этого. ( https://stackoverflow.com/questions / 19647658 / Что-то-псевдополиномиальное время - как это - это отличается - от полиномиального времени , https://stackovlow.com/whestions/4538581/Why- IS-knapsack-проблема - псевдо- полиномиальный # ответ-4538668 )

Основная вещь - это поэтому мы должны думать только «W» как «LOGW» ввод битов, а не «n» как «журнал N».

Многие объяснения сказали, что «W» - это целое число, но «n» - это просто количество элементов. Поэтому только размер «W» пропорционален «LOGW».

Я думаю, что эта логика должна быть применена к 'n'.

Предполагая, что мы нумеруем элементы от 1 до n, для дифференциации элементов,

Мы должны подсчитать количество от 1 до n.

Я думаю, что это то же самое, что цикл делает итерацию для W понции.

Поэтому я думаю, что это то же самое с «W», потому что это подсчет также нужно «журнал N».

Что я не понимаю по этой проблеме?

спасибо.

Answer 1

Вот как вы кодируете вход:

.
• вес и значение элемента 1.
• Вес и значение элемента 2.
• ...
• Вес и значение элемента $ n $ .
• $ W $ .

Предположим, что вес и значение являются целыми числами, находятся на большинстве $ m $ , и оба закодированы в двоичном, как это $ W $ .Тогда длина кодировки $$ \ Omega (n + \ log w), o (n \ log m + \ log w). $$ Надеюсь, это разъясняет разницу между $ n $ и $ W $ .