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

  • $\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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.