0
$\begingroup$

Sorry for making up a name for the thing, the main reason for posting this question is that I can't find out the name of the problem that i'm thinking about.

I was messing around with min/max DP stuff, and when looking at a knapsack problem I wondered if you could apply DP if each item affected the total value of the other items. For example:

given the input:

bag_size = 10, 
item_list = [(4,2),(1,2),(10,9),(7,6)], // (value, weight)
synergy_list = [[0, 2, 0, 0],[1,0,1,1],[0,0,0,5],[1,1,0,0]] // increment to [1st, 2nd, 3rd, 4th] 

(if you had items 1 and 2 in the bag the total value would be 8
 4 and 1 being the value of the first and second items 
 2 and 1 the value of their synergy with each other)

I assume you cannot use DP productively due to each item possibly changing the result that would be cached in the standard knapsack, forcing the recomputation. Given that, is there any approach apart from brute force? And also is there a proper name for this type of problem?

Thanks!

$\endgroup$
6
  • $\begingroup$ You need to add limits to the synergies, such as never causing a combination to go negative, otherwise you could add infinite items to the bag. $\endgroup$ Commented May 15, 2023 at 16:28
  • $\begingroup$ Are the synergies defined such that you must have a unique pair to earn the synergy? Like if items A and B get a synergy, if I add a second A do I need a second B to get a second synergy benefit? Or once I have a B do all A's bring in another increment of the synergy? $\endgroup$ Commented May 15, 2023 at 16:32
  • $\begingroup$ Please edit your question to provide a general problem specification. An example or some code is not a substitute for a specification of the problem. "each item affected ..." is very broad and there are many possible things that could meaning, depending on what types of effects you need to support or don't. I suggest you describe the algorithmic problem by specifying the inputs and the desired output. You should describe how effects/synergies are represented and what set of them can be specified in that representation. $\endgroup$
    – D.W.
    Commented May 15, 2023 at 16:34
  • $\begingroup$ I agree with D.W. There are many mathematical / algorithmic problems that look the same, but a seemingly insignificant addition or relaxation of constraints may cause the problem to be easily solvable with an efficient algorithm or become much more difficult to solve and require a brute force approach. $\endgroup$ Commented May 15, 2023 at 16:52
  • $\begingroup$ Another helpful constraint for you to specify: Is the problem a 0-1, Bounded, or Unbounded knapsack problem? $\endgroup$ Commented May 15, 2023 at 17:26

1 Answer 1

0
$\begingroup$

TLDR: Transform the problem to a standard knapsack problem, then use a standard algorithm.

Assume that if an item A is paired with an item B to earn a discount based on synergy it may not also be paired with an item C or another B to earn an additional synergy.

  1. Construct N(N+1)/2 synthetic items formed by all pairs A+B which have value as the sum of values and weight as the sum of weights adjusted by synergy discount.

  2. Discard any synthetic items that have a synergy discount of zero, as they offer no benefit over the component items.

  3. Adding this set to the original N types of item gives N(N+3)/2 total types of item, or roughy N-squared.

  4. Search for dominance relations and remove superfluous items. For example, if an item X (original or synthetic) has higher value and equal or lower weight to an original item or any other synthetic item Y, Y is superfluous; it cannot appear in an optimal solution so may be discarded, simplifying the problem.

  5. Use any knapsack algorithm, approximate or exact. The Big-O running time will be the same, just against a larger set of items N^2.

  6. Some of the tested permutations may include unpaired original items A + B that could benefit from a synergy, but the synthetic combination AB will also be tried and yield the proper total weight.

Using the above transformation of the problem , you can use dynamic programming (DP) and benefit from its speed-optimality tradeoff.

NOTE: If the up-front assumption does not hold, you need to augment the list of synthetic items with more combinations, like triples, quadruples, etc, possibly making the problem incapable of being solved in a reasonable time. In that case, this transformation will not be useful.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.