Ordering from a Menu

Computer Science Level 2

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

Let $O$ be the number of different ways that you can spend exactly $300. What are the last 3 digits of $O$ ?

The answer is 935.

7 solutions

Thaddeus Abiy
May 9, 2014

Behold the power of Dynamic Programming!

#python
ways = [1]+[0]*300 
for a in [1,5,20,50,100,200]:
    for i in range(a, 300+1):
        ways[i] += ways[i-a] 
print ways[300] % 1000

@Thaddeus Abiy Is there another way of solving this problem, using combinactorics method or algebra.I am clue less.

Mardokay Mosazghi - 7 years, 1 month ago

For CS problems,a programming solution is easier to understand. But surprisingly,for this problem there is a very mathematical solution! You can construct a generating function and read the coefficient next to $x^{300}$

Thaddeus Abiy - 7 years, 1 month ago

Oh and the function is $\frac{1}{((1 - x)(1 - x^5)(1 - x^{20})(1 - x^{50})(1 - x^{100})(1 - x^{200}))}$

Thaddeus Abiy - 7 years, 1 month ago

@Thaddeus Abiy – Thanks this is helpful

Mardokay Mosazghi - 7 years, 1 month ago

@Mardokay Mosazghi – A bit late but,Happy Birthday!

Thaddeus Abiy - 7 years, 1 month ago

@Thaddeus Abiy – In advance is this called Ordinary generating functions

Mardokay Mosazghi - 7 years, 1 month ago

Thaddeus, I don't understand how your program works. Can you explain?

Chew-Seong Cheong - 6 years, 11 months ago

Roger Erisman
Dec 18, 2015

Small BASIC

sum = 0

For a = 0 To 300

For b = 0 To 60

For c =  0 To 15

  For d = 0 To 6

    For e = 0 To 3

      For f = 0 To 1

        total = a + 5*b + 20*c + 50*d + 100*e + 200*f

        If total = 300 Then

          sum = sum + 1

        EndIf

      EndFor

    EndFor

  EndFor

EndFor

EndFor

TextWindow.Write(sum)

Agnishom Chattopadhyay
May 11, 2014

...

f = 1/((1-x)(1-x^5)(1-x^20)(1-x^50)(1-x^100)(1-x^200))

That is the generating function

Here is what you do to get the coefficient of x^300:

Coefficient[Series[f,{x,0,35}],x,300]

It gives 1935

Drop TheProblem
Oct 30, 2014

#include<iostream>
#include<stdio.h>
#include<fstream>
using namespace std;
int main(){ int conta=0;
    for(int a=0; a<=300; a++)
       for(int b=0; b<=60; b++)
          for(int c=0; c<=15; c++)
             for(int d=0; d<=6; d++)
                for(int e=0; e<=3; e++)
                   for(int f=0; f<=1; f++)
                      if(1*a+5*b+20*c+50*d+100*e+200*f==300){conta++; conta=conta%1000;}
    cout<<conta<<endl;
    system("pause");
    return 0;
}

conta=935

Navin Manaswi
May 7, 2016

R program

count = 0

for(i in seq(0,300,1)) for(j in seq(0,300,5)) for(k in seq(0,300,20)) for(a in seq(0,300,50)) for(b in seq(0,300,100)) for(c in seq(0,300,200))
if(i+j+k+a+b+c==300) count = count +1

count

Laurent Shorts
Apr 25, 2016

In Python:

VALUES = [200, 100, 50, 20, 5, 1]
TOTAL = 300

def nbWays(total, values):
        if len(values) == 1:
                if total % values[0] == 0:
                        return 1
                else:
                        return 0

        ways = 0 
        for subamount in xrange(0, total+1, values[0]):
                ways += nbWays(total - subamount, values[1:])

        return ways


print nbWays(TOTAL, VALUES)

Chew-Seong Cheong
Jul 10, 2014

I used a simple Python program to solve the problem. See below:

x=0

for i in range(2):

for j in range(4):

  for k in range(7):

      for l in range(16):

          for m in range(61):

              for n in range(301):

                  s=200*i+100*j+50*k+20*l+5*m+n

                  if s==300:

                      x+=1

                      print x,i,j,k,l,m,n

( x )2*8 + n = 25. so, we have 934 + 5 = 935.

Am Kemplin - 1 month, 2 weeks ago

Ordering from a Menu

The answer is 935.

7 solutions

R program

0 pending reports