+ 1

HEY HEY guys, can you help me find the algorithm or solve this problem?

Problem: You have in your wallet $300, which you want to spend completely. You decide to spend all of it by buying food from a fancy restaurant with the following menu: tofu scramble: $1 pancakes: $5 brunch combo: $20 saffron infused peach tea: $50 truffles: $100 caviar: $200 FIND THE NUMBER OF DIFFERENT WAYS TO SPEND ALL 300$

9th Jul 2021, 8:46 AM
TCorn
TCorn - avatar
15 ответов
+ 6
The6 trick is to forget the tofu scrambles and regard the problem to spend max 300$ What u didn't spend this way goes to tofu scrambles.so finally we spend 300$. we have to check 61×16×7x4x2 combinations which can be done by brute force even in sololearn. YUGRAJ of course dynamic programming will shorten time even more.
10th Jul 2021, 11:13 AM
Oma Falk
Oma Falk - avatar
10th Jul 2021, 11:49 AM
Pallavi Bhardwaj
Pallavi Bhardwaj - avatar
+ 8
TCorn I have done same as Oma Falk sir done with shorten code....
11th Jul 2021, 2:44 AM
Pallavi Bhardwaj
Pallavi Bhardwaj - avatar
+ 6
It is same as number of subsets having sum x, just generate or calculate sum for each subset using recursion or bitmasking and see if it is equal to sum you needed then increase counter by 1. O(2^n) complexity. Efficient way: use dynamic programming. dp(i)(j) ==> number of ways to make sum j, using some subset of elements from index 0 to i. dp(i)(j)= dp(i-1)(j)+dp(i-1)(j-a(i)) //answer will be dp(n-1)(sumNeeded) O(n*sumNeeded) complexity
9th Jul 2021, 9:27 AM
Gaurav Agrawal
Gaurav Agrawal - avatar
10th Jul 2021, 11:32 AM
Oma Falk
Oma Falk - avatar
+ 3
recursion
9th Jul 2021, 8:53 AM
Gordon
Gordon - avatar
+ 3
We can use dynamic programing to solve this there will be two states of dp first is item's index second total money spend till now
9th Jul 2021, 9:02 AM
YUGRAJ
+ 3
TCorn a very little adjustment and it works😜
10th Jul 2021, 11:07 AM
Oma Falk
Oma Falk - avatar