Geek Answers Handbook

Can I use dynamic programming to solve this problem?

I have very little experience in dynamic programming. I used it to solve the DNA alignment problem, the problem with the main backpack and the simple problem of finding paths. I understood how they work, but I don’t feel absolutely comfortable.

I have a problem that reminds me of dynamic programming 0-1, but the differences have thrown me away and I'm not sure if I can use this technique or if I have to agree to a recursive approach.

Let's say I have a list of items, each of which has different meanings, weight and costs. There may be more than one item.

Let's say I need to choose combos from those items that are the most valuable, but remain within the range of weight and cost. So far, I have described a backpack problem, to a large extent, with two limitations. But here is the difference:

The value of the selected item changes depending on how many of them I have in the combo.

Let's say that each element has a function associated with it, which tells me which group of these items is worth me. This is a basic linear function such as value_of_item = -3 (the amount of this element) + 50

So, if I have one element in a combo, then for me this value is 47. If I had 2 of them, then they are only 44 for me.

If for this I use a dynamic programming table, then for each cell I will need to step back to see if this element is in the current combo, which makes DP pointless. But maybe there is a way to redo the problem so that I can use DP.

Hope that made sense.

An alternative is to create each combination of elements, within cost and weight, to determine the value of each combo, select the most valuable combo. For a list of 1000 items, even this will be an expensive search, and this is what I will count many times. I would like to find a way to take advantage of DP.

+6
source share
1 answer

If your functions have the form

value(x, count) = base(x) - factor(x) * count, factor(x) > 0,

then you can reduce the problem to a standard backpack by dividing the elements:

 x -> x_1 to x_max_count value_new(x_i) = value(x, i) weight(x_i) = weight(x)

Now you can easily make sure that no optimal solution for a new problem uses any element x_j , without using every x_i with i <k.

Evidence. Contradiction: suppose that there exists such an optimal solution S and it uses x_j , but not x_i , j> i. Then there is an alternative solution S 'that uses x_i instead of x_j . Since j> i,

 value_new(x_j) = value(x, j) = base(x) - factor(x) * j < base(x) - factor(x) * i = value(x, i) = value_new(x_i)

and therefore S 'has a higher value than S, and we have reached a contradiction.

In addition, we can enable factor(x) = 0 , this corresponds to the standard elements of the knapsack.

However, if there is a form limitation

 value(x, count) = base(x) + factor(x) * count

where factor(x) is an arbitrary value, the above solution no longer works, because the last element will be the one with the highest value. Perhaps some complex modification of DP may allow you to use such restrictions, but I do not see any changes to the problem itself to use DP immediately.

Some studies on this topic (more general):

0
source

More articles:


All Articles