+ 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$

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.

+ 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

+ 3

recursion

+ 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

+ 3

TCorn a very little adjustment and it works😜