Timeline for Knapsack with a fixed number of weights
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 19, 2022 at 2:47 | history | edited | Erel Segal-Halevi | CC BY-SA 4.0 |
added 382 characters in body
|
| Sep 1, 2020 at 10:45 | vote | accept | Erel Segal-Halevi | ||
| Dec 19, 2022 at 2:52 | |||||
| Dec 8, 2019 at 20:51 | answer | added | gnasher729 | timeline score: 3 | |
| Dec 8, 2019 at 16:02 | answer | added | j_random_hacker | timeline score: 1 | |
| Dec 8, 2019 at 13:06 | comment | added | j_random_hacker | A better criterion for a greedy algorithm is the ratio of value to weight: $v_i/w_i$. Ordering by this in descending order exactly solves the fractional version of the Knapsack problem, where we are allowed to take any fraction between 0 and 1, inclusive, of any item (take 1 of each item until the first item that doesn't completely fit; take as much of it as will fit). As this is a relaxation of the 0-1 Knapsack problem, the total value of it is an upper bound on the total value of the 0-1 variant, so the same greedy algorithm (but skipping the partial item) is a good heuristic for 0-1. | |
| Dec 7, 2019 at 18:12 | history | asked | Erel Segal-Halevi | CC BY-SA 4.0 |