Interview question

general
1

Modified Knapsack
An array of the following products are given
i) Cost [1, 1, 2] //Cost of each product to buy
ii) Happiness [2, 3, 1] //Happiness after buying each product
iii) MinQuantity [2, 1, 1] //MinQuantity to be bought in each product
iv) MaxQuantity [4, 3, 2] //MaxQuantity to be bought in each product
v) Money (4) //Total available money
Return the max happiness possible. Answer=-1

Can anyone share the approach?

2

It’s a Linear/Integer programming question.

If you buy quantities x, y and z of the products, then:

Cost constraint: x+y+2z \le 4

Happiness function: maximize 2x + 3y + z

Min Constraints: x \ge 2, y \ge 1 and z \ge 1

Max Constraints: x \le 4, y \le 3 and z \le 2

Unfortunately, the cost of the minimum quantities exceeds Money available, so doesn’t look as though you can achieve any happiness.

3

ok but can you say the approach for the question, not for the example given i.e how to solve programatically?

4

Its a Linear programming question. Big subject area.

The Simplex algorithm is the first listed in wikipedia, and was certainly the first, probably only, general method I met in college.

In an interview I guess the thing to show is that you know how to express it as a linear programming problem. How to introduce slack variables. The concept of a feasible solution (which is a solution that meets the constraints but doesn’t have to optimize the happiness function).

To solve it, go to the internet and get a free linear programming tool.

5

@meooow can u try this?

6

Can u explain how come 8 is the ans? I mean u’ve written min quantity to be brought is 2,1,1 whose costs comes 2*1+1+2=5 > 4

7

I can solve this using dp,provided u clarify the question.

8

@ yes the answer should not be 8 my bad, explain the approach?

9

First lets do some simplification.

We would obviously always need to buy the min quantity for all products;

So first just calculate the happiness(lets say x) when u buy min quantities.

Lets say in ur case ,x=2*2+3+1=8,and also change the amountLeft=InitialAmount-totalCost=InitAm-5(in ur case)

So now we can buy at most maxQuantity[i]-minQuantity[i] products of i.

So change maxQuantity[i]=maxQuantity[i]-minQuantity[i]

So the question now simplifies to find max haappiness when u can use <=maxQuantity[i] for each i

let dp[i][m] denote the maximum happiness u can get using first i elements and using exactly m rupees

So recurrence:

dp[i][m]=max((for j=0 to maxElement[i])dp[i-1][m-j*cost[i]]+j * happiness[i])

//if u take 0 elements,1 elements,…maxElement[i] of i

FinalAns=x+(max(dp[n][j]) where j=0 to amountLeft)

1 Like
10

According to me the maximum happiness will be 10.
2×2+3×2 =10…how the ans come 8???

11

You can convert this problem to the standard knapsack problem. First, buy all the items the required (MinQuantity) number of times. Decrease the money accordingly. Now, you can buy each of the items T = MaxQuantity - MinQuantity times. This is same as having ‘T’ copies of each of those items. So, create a new set of items, with each item appearing T[i] times.

You can further improve the complexity by reducing the number of items in the new item set. Suppose that you can have 100 copies of some item, rather than adding this item 100 times, you can add groups having sizes equal to powers of 2. So, you would add items corresponding to 1,2,4,8,16,32…copies, and subtract them from 100, finally add one more item corresponding to the remaining number of copies (100 - (1+2+4+8+16+32) = 37). This reason why this will work is: if the solution contains ‘X’ copies of some item, this number ‘X’ can be made up using powers of 2.

After that, you can solve it using DP. DP[i][j] will be the max happiness you can get using the first ‘i’ items and spending ‘j’ units of money. DP[i][j] = max ( DP[i-1][j], DP[i-1][j-cost[i]] ).

1 Like
12

could u plz tell is my idea correct or not?

13

Its correct

14

@hemanth_1 Can you please elaborate on the optimization part, I am still trying to figure out what you stated over there.

15

Suppose that you have an item with cost = 1 happiness = 2 and you can use it 100 times at most.These will be your arrays for cost and happiness :

C[] = 1 1 1 1 1 …repeated 100 times

H[] = 2 2 2 2 2 …repeated 100 times

What will be the possible combinations that you can get using some subset of these items ? lets denote a combination as a pair <cost,happiness>. You will be able to get : <1,2>,<2,4>,<3,6>,…,<100,200>. What if you take these :

C[] = 1 2 4 8 16 32 37

H[] = 2 4 8 16 32 64 74

You can still make all of those, but there are less number of items now.

16

@hemanth_1 I know how to do for standard knapsack where there are infinitely many but how to solve for limited number of quantities, can u please explain clearly ?

17

What I mentioned is for limited quantities. Even in the example I have taken, there is a limit right ? I can only take 100

18

@vivek_1998299 what is the time complexity of your solution?

19

O(n * (max(maxElement)) * money)

Though u can replace max(maxElement) by log factor using optimisations suggested by hemanth