Hackerearth | Nothing But Code - Hiring Challenge | Help

, ,
1

Can someone tell me how to solve this question which is taken from the Hackerearth challenge(already expired) Nothing But Code - Hiring Challenge

There are N jewellery shop. Each jewellery shop has three kinds of coins - Gold, Platinum, and Diamond having worth value A, B, and C respectively. You decided to go to each of N jewellery shop and take coins from each of the shop. But to do so following conditions must satisfy -

You can take at most 1 coin from an individual shop.
You can take at most X coins of Gold type.
You can take at most Y coins of Platinum type.
You can take at most Z coins of Diamond type.
You want to collect coins from shops in such a way that worth value of coins collected is maximised.

Input Format :

The first line contains an integer N. Where N is the number of jewellery shops.
The second line contains three integers X, Y, Z. Where X, Y, Z denotes the maximum number of coins you can collect of type Gold, Platinum, and diamond respectively.
Then N lines contain three space-separated integers A, B, C. Where A, B, C is the worth value of the Gold, Platinum, and diamond coin respectively.

Output Format :

Print a single integer representing the maximum worth value you can get.

Constraints :

1 <=N <= 200

1 <= X,Y,Z <= N

1<= A,B,C <10^9

Sample Input

4
2 1 1
5 4 5
4 3 2
10 9 7
8 2 9

Sample Output

27
1 Like
2

It looks like a modification to knapsack would solve it.

Let’s define our dp table as 4-dimensional array dp[N+1][A+1][B+1][C+1]

Now some cell dp[n][a][b][c] means that we have considered n shops, out of them we picked ‘a’ shop(s) for Gold, ‘b’ shop(s) for cake and ‘c’ shop(s) for pizza and it stores max energy we can have.

Transitions are easy too, from some state dp[n][a][b][c] we can move to:

  • dp[n+1][a][b][c] if we skip n+1 shop
  • dp[n+1][a+1][b][c] if we buy meat from shop n+1
  • dp[n+1][a][b+1][c] if we buy cake from shop n+1
  • dp[n+1][a][b][c+1] if we buy pizza from shop n+1

All that’s left is to fill dp table. Sample code:

N = 10
A,B,C = 5,3,2
energy = [
[56, 44, 41],
[56, 84, 45],  
[40, 98, 49],  
[91, 59, 73], 
[69, 94, 42], 
[81, 64, 80], 
[55, 76, 26], 
[63, 24, 22], 
[81, 60, 44], 
[52, 95, 11] 
]

dp = {} 

for n in range(N+1):
    for a in range(A+1):
        for b in range(B+1):
            for c in range(C+1):
                dp[n,a,b,c]=0

answer = 0;
for n in range(N+1):
    for a in range(A+1):
        for b in range(B+1):
            for c in range(C+1):
                #Case 1, skip n-th shop
                if (n+1,a,b,c) in dp: dp[n+1,a,b,c] = max(dp[n+1,a,b,c], dp[n,a,b,c])
                #Case 2, buy meat from n-th shop
                if (n+1,a+1,b,c) in dp: dp[n+1,a+1,b,c] = max(dp[n+1,a+1,b,c], dp[n,a,b,c] + energy[n][0])
                #Case 3, buy cake from n-th shop
                if (n+1,a,b+1,c) in dp: dp[n+1,a,b+1,c] = max(dp[n+1,a,b+1,c], dp[n,a,b,c] + energy[n][1])
                #Case 4, buy pizza from n-th shop
                if (n+1,a,b,c+1) in dp: dp[n+1,a,b,c+1] = max(dp[n+1,a,b,c+1], dp[n,a,b,c] + energy[n][2])
                answer = max(answer,dp[n,a,b,c])

print(answer)

hAPPY CoDING!:slight_smile:

2 Likes
3

oops . 5* find it hard , i should immediately change my color to red .
btw i answered ur query on codeforces

5

200 * 200 * 200 * 200 = 16 * 10 ^ 8 = 1.6 * 10 ^ 9 , this is not codeforces server so i am assuming u r using supercomputer .
remove first state .

6

You can easily remove 1-dimension from the dp.

7

If you can help,its okay.No need to belittle other people.
Learn human values and ethics atleast or don’t bother posting toxic comments.

8

is this referring to oops 5* or 200*200 comment :slight_smile::slight_smile:

9

Then how will you gonna remove that one state?

1 Like
10

Read this:- A Space Optimized DP solution for 0-1 Knapsack Problem - GeeksforGeeks

11

which comment ? ???

12

@anon55659401 This will only optimise the space not time.
Read this article carefully

13

Bhai,thoda optimization khud bhi karle:-) Sab mai hi karu kya? :stuck_out_tongue: Itne idea bataaye uska shukar kar:p