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!


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.