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

Question

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$

Answer 1

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.

Answer 2

https://code.sololearn.com/cS58xa1vMtUc/?ref=app

Answer 3

TCorn I have done same as Oma Falk sir done with shorten code....

Answer 4

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

Answer 5

https://code.sololearn.com/cgRiLRRcR7oy/?ref=app

Answer 6

recursion

Answer 7

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

Answer 8

TCorn a very little adjustment and it works😜

Answer 9

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

Answer 10

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$

Answer 11

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

Answer 12

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

Answer 13

How to use dynamic programming broooo

Answer 14

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

Answer 15

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