-3

I have the same problem as here: Variation on knapsack - minimum total value exceeding 'W' with an added constraint.

Details:

We have a group of items, each item (i) has a weight (w_i) and a value (v_i) and a price(p_i). We have to select a subgroup of these items such that:

  • minimize the total aggregate value

s.t.

  1. total aggregate weight is at least W.
  2. total aggregate price is at most P.

If we ignore the last constraint, this is equivalent of 0/1 knapsack problem and can be solved as amit mentioned in the question linked above. With the addition of last constraint is it still solvable using dynamic programming ?

Any tips are appreciated.

Community
  • 1
  • 1
Bonaqa .
  • 1
  • 1
  • 1
    Probably more suitable for http://cstheory.stackexchange.com/. In any case you are clearly looking for homework solutions in a rude (and mostly lazy) way. – Jack Jun 11 '12 at 16:53
  • wrong guess Jack. Its not a homework, its simplified version of a real life problem and is not easy. If you think its straight forward, try solving it and I know you will be convinced. – Bonaqa . Jun 11 '12 at 17:02

2 Answers2

0

Since it is a NP-hard problem, you just have to test all cases.

Thomash
  • 6,339
  • 1
  • 30
  • 50
  • The Knapsack problem is also NP-hard, but it still has better solutions than brute-force. – ffao Jun 11 '12 at 17:39
  • @Thomash: This is not the original knappsack problem, but a knappsack problem with an additional constraint. Although I would guess it is still NP-hard, I cannot find a proof and neither did you present one, so we shouldn't be 100 percent sure. Adding additional constraints can change an NP-hard problem to become an element of P. At first sight this seems contra-intuitive since one would not suspect that adding an additional constraint can make a problem easier, but this is actually the case if the search-space becomes limited enough. – LiKao Jun 11 '12 at 17:53
  • Brute force is not really an (feasible) option, because the actual problem relates to data centers that can actually have 1000s of different power configurations causing explosion of search space. I was searching for dynamic programming approach to it to atleast get pseudo polynomial time algorithm, but due to this extra constraint, I am having problem in determining the optimal substructure. – Bonaqa . Jun 11 '12 at 20:56
0

An obvious solution is to use two variables in your dynamic programming state, W (current weight) and P (current price), such that m[W][P] gives the best value with those two parameters. This would give you an algorithm which runs in O(nP * sum of weights).

You might also want to consider the complementary solution (inverting W and P, as in amit's answer), depending on whether (sum of weights) * P or W * (sum of prices) is bigger.

ffao
  • 856
  • 4
  • 7