Problem

[harsh4u89]

Given a soda-lime machine. It has three buttons.

pressing First button gives 230-250 ml of soda

pressing Second button gives 290-310 ml of soda

pressing Third button gives 500-515 ml of soda

The exact amount of soda that comes out pressing this button is not fixed and lies in the range given above.

The question is write a program to calculate the order of buttons required to be pressed to get a soda equal to an amount that lies between MIN and MAX values specified.


Every button can be pressed multiple times.


What would be the best approach for this

Please discuss the algorithmic approach.

Regards

[Bazzy]

rand() returns a (pseudo) random number between 0 and RAND_MAX
http://www.cplusplus.com/reference/clibrary/cstdlib/rand/
rand() % n returns a number between 0 and n ( n exclusive )
rand() % n + m between m and n+m

[amzsingh]

dear harsh4u89 and Bazzy,

if you use random function then there no way to have MIN or MAX because random function would work differently on each computer and its a random number. Its not fixed that you would get the MAX number at an N times

Your question is a little confusing as in you want the order of buttons to be pressed ??

[chrisname]

@amzsignh,
Bazzy gave a way to specify a minimum and maximum number:

template <typename T>
T random(T min, T max)
{
        return T(rand() % min + max);
}

[Bazzy]

The code above is not exact, it will generate numbers in [min,min+max)

[amzsingh]

but thats not what the Question asks....

it asks about the order of buttons....

[m4ster r0shi]

I think I understand what he wants. You give a min and a max and then you want to find which linear combinations of the buttons can give you a total result between these values.

e.g.

if you give min=500, max=700 there are 3 solutions:

1*B1 + 1*B2 + 0*B3 which gives a range of [520,560]
0*B1 + 2*B2 + 0*B3 which gives a range of [580,620]
0*B1 + 0*B2 + 1*B3 which gives a range of [500,510]

if you give min=1000, max=1100 there are 2 solutions:

1*B1 + 1*B2 + 1*B3 with a range of [1020,1070]
0*B1 + 0*B2 + 2*B3 with a range of [1000,1020]

and if you give min=400, max=450 there is no solution.

You can simply brute force this. Let's say you want to find all possible a1, a2 and a3 so that the following is true:

min <= a1*B1 + a2*B2 + a3*B3 <= max

Obviously it should be ai>=0. Another, also obvious, restriction is ai<=1+max/Bi ai<=1+max/Bi.max. These are enough. You can then write a 3-level for loop with each ai iterating through its available values and keep those linear combinations that give the wanted result.

Though, the 'order of buttons' is a bit confusing, since this doesn't seem to affect the solution... Maybe he means something slightly different. I guess he'll have to elaborate...

[Kyon]

I believe by order he refers to sets of solutions by themselves, not the lower-level sorting of these solutions. He just put it wrong a tad bit.

[m4ster r0shi]

Yes, I guess that would explain it. Let's see what he has to say.

[sehrish]

hi friend,
i think u can start it thus,
#include<iostream.h>
main()
char c,
cout<<"Enter F for first choice";
cout<<"Enter S for second choice";
cout<<"Enter T for third choice";
cout<<"Enter your choice";
cin>>choice;
switch(c);
{
case 'f':
case 'F':
cout<<"you choice is 230-250 ml of soda";
break;
case 's'
case 'S';
cout<<"your choice is 290-310 ml of soda";
break;
case 't';
case 'T';
cout<<"your choice is 500-515 ml of soda";
break;



hope it can help, if u need more then tell briefly.
regard,
sehrish

[1yR4jE8b]

The first way that springs to mind is to just press Button 3 until you don't have enough room left to take another 500-515ml, then press button 2 until you don't have room left for that amount(which may be 0 presses), and then button 1 for that amount(which may be 0 press).

The problem doesn't specify the OPTIMAL solution, so this approach is simple and effective.

[1yR4jE8b]

It's also not asking for 'all possible solutions', just one solution.

[harsh4u89]

Sorry , I made a mistake by writting order of buttons

The answer can be in the form of an array, say Solution , such that


Solution[0] , gives the number of presses of first button.
Solution[2], gives the number of presses of button second.
Solution[3] ,gives the number of presses of third button.

Can we use dynamic programmming for this?