I have a problem that is 0/1 knapsack, but you are also able to swap the weight of 2 items up to k times. I came up with a O(nkc) solution, but I am looking for a faster o(n*c) solution. I think the intuition is we should use all k swaps unless we can use less than k swaps and use all of the max values with the minimum weights. I just need help on the using all k swaps part
1
-
$\begingroup$ What is c? Please define all notation. Can you show us your $O(nkc)$ time algorithm? Please proof-read your post -- the typesetting in $O(n*k*c)$ didn't work out the way you intended, due to Markdown. $\endgroup$– D.W. ♦Nov 20 at 6:23
Add a comment
|