All geek questions in one place

Formation of a dynamic programming algorithm for varying a knapsack problem

So I thought

I would like to make a variation of the Knapsack problem.

Imagine the original problem with items with different weights / values.

My version, along with normal weights / values, contains the value "group".

eg. Item1 [5kg, $ 600, electronic] Item2 [1kg, $ 50, food]

Now, having a set of such elements, as if I encoded a problem with a backpack, to make sure that no more than 1 element is selected from each "group".

Notes:

  • You do not need to select an item from this group.
  • Each group has several elements.
  • You still minimize weight, maximize value
  • The number of groups is predetermined along with their values.

I am just writing a draft code at this point, and I decided to use a dynamic approach. I understand the idea of ​​a dynamic solution for a common backpack problem, how do I change this solution to include these “groups”?

KnapSackVariation(v,w,g,n,W) { for (w = 0 to W) V[0,w] = 0; for(i = 1 to n) for(w = 0 to W) if(w[i] <= w) V[i,w] = max{V[i-1, w], v[i] + V[i-1, ww[i]]}; else V[i,w] = V[i-1, w]; return V[n,W]; }

This is what I still have, I need to add it so that it removes all the relevant elements from the group in which it is located every time it solves this.

+6
source share
2 answers

Suppose
c [i]: category of the i-th element
V [i, w, S]: the maximum value of a backpack is such that it contains a maximum of one element from each category in S

 Recursive Formulation V[i,w,S] = max(V[i-1,w,S],V[i,ww[i],S-{c[i]}] + v[i]) Base Case V[0,w,S] = -`infinity if w!=0 or S != {}`
0
source

just noticed your question trying to find the answer to your question. The problem you have stated is a well-known and well-studied problem, called the multiple choice problem. If you are Google, you will find all kinds of information, and I can also recommend this book: http://www.amazon.co.uk/Knapsack- Problems-Hans-Kellerer / dp / 3642073115 / ref = sr_1_1? Ie = UTF8 & qid = 1318767496 & sr = 8-1 , which devotes a whole chapter to this problem. In the classic MCKP wording, you need to select one element from each group. However, you can easily convert this version of the problem into your version by adding a dummy element to each group with a profit and weight = 0, and the same algorithms will work. I would caution you against trying to adapt the code for a binary backpack problem to MCKP with a few settings - this approach will most likely lead you to a solution whose performance decreases unacceptably as the number of elements in each group increases.

+3
source

Source: https://habr.com/ru/post/898812/

More articles:


All Articles