0
$\begingroup$

I recently was looking at the knapsack problem and was wondering, if a slight modification can be done.

Let's say that if my bag is empty, I have values $[x_{10},x_{20},x_{30},... ,x_{n0}]$ for n items. But when item i is chosen as a first in the bag, the values change to $[x_{1i},x_{2i},x_{3i},... ,x_{ni}]$. The values change everytime, when I put new items in the bag. Let's also assume that I have the function, how the values change.

Does anyone know how to modify the algorithm to this case? I saw a version of a "greedy" algorithm and it gave me an idea. I would just divide the value by the weight, choose the item that has the biggest ratio. The values would recalculate again, then I would choose the biggest ratio again etc etc. This however doesn't take into consideration that by choosing a smaller value/weight for item i at time t-1 can yield a bigger value at time t. This might yield a bigger total value/weight then by choosing item j at time t-1 that had a bigger value/weight.

Thanks in advance, hopefully some can help me with this problem!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.