Timeline for 0-1 knapsack without repetition
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 22, 2020 at 15:07 | comment | added | nimdraks | I finally understand it. I love you. thank you so much! | |
| Apr 22, 2020 at 15:07 | vote | accept | nimdraks | ||
| Apr 22, 2020 at 15:06 | comment | added | Yuval Filmus | The time complexity depends on the encoding. We usually use binary encoding, in which case what you wrote is correct. If $W$ is encoded in unary then we do get a polynomial time algorithm. This is the real meaning of "pseudo-polynomial time algorithm". | |
| Apr 22, 2020 at 15:05 | comment | added | nimdraks | Then is it right? Time complexity is actually decided by the input length(input size) in binary encoding. At 'W', its size is logW due to its binary encoding but in the 'n' case, it is just n because it is just a list. it's like unary encoding. | |
| Apr 22, 2020 at 14:57 | comment | added | Yuval Filmus | The input length is proportional to $n + \log W$ (neglecting $M$). Therefore counting from $1$ to $n$ takes polynomial time, but counting from $1$ to $W$ could take exponential time, if $W$ is very large compared to $n$. | |
| Apr 22, 2020 at 14:56 | comment | added | nimdraks | Thanks. But I have a question. but I'm confused yet. Assume n is same with W. Then n items list iteration is same with W times iteration, in terms of the number of iteration. is it right? | |
| Apr 22, 2020 at 14:24 | history | answered | Yuval Filmus | CC BY-SA 4.0 |