Spend As Much As You Can - Part 1

Since this is a computer science problem, here's an algorithm I wrote in Python to solve this problem.

price = 0    #let this be the calculated total price
prices = []    #let this be the array containing all possible prices

#let a,b, and c be the quantity of each item bought

for a in xrange(0, 10):
    for b in xrange(0, 10):
        for c in xrange(0, 10):
            price = (a*0.59)+(b*0.79)+(c*0.95)
            if  price <= 4.0:
                prices.append(price)

print max(prices)

The programme returns 3.95 as the answer.

Although the scale of the problem allows for heuristics such as those given in the other answers to be applied to arrive at an educated guess, the problem admits a correct solution via dynamic programming. Since once is not able to arrive at any valid greedy methods to maximize utility in this problem, one has to rely on a weak structure present in the problem that is informally given below

"The maximum expenditure must be incurred by first spending money on buying one unit of licorice, drops or bears and then spending the rest of the money most effectively".

Thus, one goes over all (3) possible choices of the first candy to buy

Candy bought (Money remaining)

• Licorice ($3.41)
• Drops ($3.21)
• Bears ($3.05)

Now one recursively finds the best ways one can spend $3.41, $3.21 and $3.05. Let those numbers be $x, $y and $z (i.e. given $3.41, I can at best spend $x out of it and so on), then the final answer can simply be arrived at by taking $\max(3.41+x,3.21+y,3.05+z)$

Now although there is scope for improving the recursive solution by memoization techniques, this is not required for this toy problem. The final solution is $3.95 which can be spent by buying 5 drops.

A simple solution in C++ :

int main()
{
    float limit = 4 , costA = 0.59 , costB = 0.79 , costC = 0.95;
    float maxCost = 0;
    float totalCost = 0;
    float x,y,z;
    for(x = 0; costA*x < limit ; ++x)
    {
        for(y = 0 ; costA*x + costB*y < limit ; ++y)
        {
            for(z = 0 ; costA*x + costB*y + costC*z < limit ; ++z)
            {
                totalCost = costA*x + costB*y + costC*z;
                if(totalCost < limit)
                    maxCost = std::max(maxCost,totalCost);
            }
        }
    }
    cout << maxCost << endl;
    return 0;
}

Actually, if you observe the choices, you will find all of them are multiples of 5 in cents. Thus, if Gina was to buy licorice, she would have to buy a multiple of 5. The same goes for chocolate drops. So we have to consider some cases.

Case 1: She buy 5 licorice and gummy bears. She would have spend 3.90 dollars. Case 2: She buy 5 chocolate drops. She would have spent 3.95 dollars. Case 3: She buy 4 gummy bears. she would have spent 3.90 dollars.

Thus the maximum money she would have spent is 3.95 dollars.

i = X = Y = 0

while i <= 6:

j = 0

while j <= 5:

    k = 0

    while k <= 4:

        X = i*0.59 + j*0.79 + k*0.95

        if X > Y and X <= 4.00: Y = X

        k = k + 1

    j = j + 1 

i = i + 1

print Y

This is my python code: S=0.0 a=0.0 while(a<=4.0): b=0.0 while(b<=4.0): c=0.0 while(c<=4.0): T=a+b+c if(T>S and T<=4.0): S=T c=c+0.95 b=b+0.59 a=a+0.79 print 'Max is %.2f'%S

The choices are all divisible by 5 so the Licorice and Chocolate drops have to be bought in fives in order to make a multiple of 5. Note that 5 Chocolate drops cost 79x5=395,knocking out 380 and 385. We see that 400 in not a nonnegative linear combination of 59x5=295, 79x5=395, and 95. (This is because the smallest combination is 95+295=390 and the second smallest is 95+395=490.) Therefore the answer is 395. (All numbers are in cents.)

Simple !! My solution in python

     list=[]

     for i in range(8):

            for j in range(4):

                    for k in range(4):
                             if 0.59*i+0.79*j+0.95*k<4:

                                    list.append(0.59*i+0.79*j+0.95*k)

        print max(list)

My solution is kinda verbose. At the end it shows the answer and the correct combination of the products required to buy. I used python for the solution. If anyone has anything to improve this I will appreciate.

import math

lic = 0.59
choc = 0.79
gum = 0.95
total = 4.00

def buyable (item):
    return math.ceil(total/item)

d = {}

for i in range(buyable(choc)):
    for j in range(buyable(candy)):
        for k in range(buyable(gum)):
            x = i*lic + j*choc + k*gum
            if (x <= total and x >= (total - 1)):
                print("{} Lic, {} Choc, {} Gum : Total = {}".format(i, j, k, x))
            prep_val = "{} lic, {} choc, {} gum".format(i, j, k)
            d[x] = prep_val
        k += 1
    j += 1
i += 1

print("Answer")
print(max(d.keys()))
print(d[max(d.keys())])

Running the Script:

0 Lic, 0 Choc, 4 Gum : Total = 3.8
0 Lic, 1 Choc, 3 Gum : Total = 3.6399999999999997
0 Lic, 2 Choc, 2 Gum : Total = 3.48
0 Lic, 3 Choc, 1 Gum : Total = 3.3200000000000003
0 Lic, 4 Choc, 0 Gum : Total = 3.16
0 Lic, 5 Choc, 0 Gum : Total = 3.95
1 Lic, 0 Choc, 3 Gum : Total = 3.4399999999999995
1 Lic, 1 Choc, 2 Gum : Total = 3.28
1 Lic, 2 Choc, 1 Gum : Total = 3.12
1 Lic, 3 Choc, 1 Gum : Total = 3.91
1 Lic, 4 Choc, 0 Gum : Total = 3.75
2 Lic, 0 Choc, 2 Gum : Total = 3.08
2 Lic, 1 Choc, 2 Gum : Total = 3.87
2 Lic, 2 Choc, 1 Gum : Total = 3.71
2 Lic, 3 Choc, 0 Gum : Total = 3.55
3 Lic, 0 Choc, 2 Gum : Total = 3.67
3 Lic, 1 Choc, 1 Gum : Total = 3.51
3 Lic, 2 Choc, 0 Gum : Total = 3.35
4 Lic, 0 Choc, 1 Gum : Total = 3.3099999999999996
4 Lic, 1 Choc, 0 Gum : Total = 3.15
4 Lic, 2 Choc, 0 Gum : Total = 3.94
5 Lic, 0 Choc, 1 Gum : Total = 3.8999999999999995
5 Lic, 1 Choc, 0 Gum : Total = 3.7399999999999998

Answer
3.95
0 lic, 5 choc, 0 gum

my perl script which approaches this is a general problem , by iterating over all possible choices and then adding them to the @cost array only if the total cost is less than total money #!/usr/bin/perl use warnings use strict; use List::Util qw[min max]; my $chocolate=0.79; my $licorice= 0.59; my $gummi= 0.95; my $money=4; my $maxcho=int($money/$chocolate); my $maxlic=int($money/$licorice); my $maxgummi=int($money/$gummi); my @cost; my $maxcandy=max($maxcho,$maxlic,$maxgummi); for my $i(0..$maxcandy) for my $j(0..$maxcandy){ for my $k(0..$maxcandy){ #push to the cost only if cost less than total money push @cost,($i $chocolate)+($j $licorice)+($k $gummi) if ($i $chocolate)+($j $licorice)+($k $gummi)<=$money; } } } print max(@cost),"\n";

public class Question1 { public static void main(String[] args) { double d; double bigger = 0; for (int i=0;i<6;i++) { for (int j=0;j<5;j++) { for(int k=0;k<4;k++) { d=(i .59)+(j 0.79)+(k*.95); if(d>bigger && d<4) { bigger=d; } } } } System.out.println("The maximum spend can be"+bigger); }

}

You can show $3.95 works with 5 chocolate drops. The only other choice that could possibly be correct is $4.00 but it can't work.

If Gina spends $4.00, she must either buy only gummy bears or 5 licorice/chocolate drops and the rest as gummy bears to make the money she spends divisible by 5 (buying 10 licorice/chocolate drops exceeds $4). If she buys only gummy bears, she will only spend $3.80. If she buys a mix of 5 licorice and chocolate drops, she will spend a value from $2.95 to $3.95, with increments of 20 cents. The only way she could buy gummy bears is when she spends $2.95, and adding 95 cents to that doesn't get as close to $4 as buying 5 chocolate drops for $3.95.