0
$\begingroup$

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

Improve this question
$\endgroup$
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. ♦
    Commented Nov 20, 2023 at 6:23

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.