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

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

+ 2

We can, you just have to help us by showing your attempt

+ 2

TCorn
if u have 1$ you buy a tofu
if u have 2$ u buy 2 tofu
...
if u have 5$ u buy a pancake or a tofu and all u can do with 5$
...
do that with each $ up to 300$

+ 1

Ohh now I have understood , thanks a punch Oma Falk
https://code.sololearn.com/cx7oqgbSiTIq/?ref=app

0

Pallavi Bhardwaj no prob son. Give your last line one more 0 and u get all digits, also the missing one
935 vs.1935

0

How to use dynamic programming broooo

0

How can you do that Shizuka(Pallavi Bhardwaj)???

- 2

Yeah Slick this is my code . But not work
codw = 0
for a in range(0,30):
for b in range(0,60):
for c in range(0,15):
for d in range(0,6):
for e in range(0,3):
for f in range(0,1):
if (a*1 + b*5 + c*20 + d*50 + e*100 + f*200) == 300:
codw += 1
print(codw)
https://code.sololearn.com/cx7oqgbSiTIq/?ref=app