Please check code for Minimum money needed problem

#1
#2

hello @sahilkhan2312000131

a) make sure when u are doing w%i or w/i then i should not be 0.

also this greedy solution will not work .
this problem is exaclty same as 0-n knapsack so try to do it in that way(all u need to do is first discard all weights with -1 price and then apply 0-n knapsack on remaining )

#3

Coding Blocks IDE
Please check the code

#4

check now->

in wt array u r storing price and not weight.

wight of ith bag is i+1 (becuase 0 based indexing)

#5

hey @aman212yadav I tried solving the problem using the method discussed in hint video. But I am getting wrong answer. I think Please check the code. Would be of great help.
Coding Blocks IDE

#6

check now->

we need to minimize the cost, u were taking max.

#7

I have 1 doubt: shouldn’t this approach be wrong because are solving it like 0-1 Knapsack where each element is available for once whereas in this question we are given an infinite number of same packets.

#8

no its not wrong

dp[i][j]=min(dp[i-1][j],wt[i-1]+dp[i][j-i]);    // LOOK here we are not doing i-1 in the last term i.e we are still considering ith bag to construct j-i weight

if we solve it like 0-1 knapsack then here it should be

dp[i][j]=min(dp[i-1][j],wt[i-1]+dp[i-1][j-i]);//note i-1

read about 0-n knapsack for better clarity

#9

Can you explain the difference between them a little more as I am not able to understand it completely.

#10

bro first solve
O-N knapsack then only u will get this.

#11

I have solved O-N knapsack

#12

then whats the issue, this problem is O-N knapsack only

#13

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.