# Milk Man and His Bottles

A Milkman serves milk in packaged bottles of varied sizes. The possible size of the bottles are {1, 5, 7 and 10} litres. He wants to supply desired quantity using as less bottles as possible irrespective of the size. Your objective is to help him find the minimum number of bottles required to supply the given demand of milk.
Input Format:
First line contains number of test cases N
Next N lines, each contain a positive integer Li which corresponds to the demand of milk.
Output Format:
For each input Li, print the minimum number of bottles required to fulfill the demand
Constraints:
1 <= N <= 1000
Li > 0
1 <= i <= N
Sample Input and Output
SNo. Input Output
1
2
17
65
2
7
Explanation:
Number of test cases is 2
1. In first test case, demand of milk is 17 litres which can be supplied using minimum of 2 bottles as follows
o 1 x 10 litres and
o 1 x 7 litres
2. In second test case, demand of milk is 65 litres which can be supplied using minimum of 7 bottles as follows
o 6 x 10 litres and
o 1 x 5 litres

#### john

• Aug 7th, 2015

```Codeint main()
{
int n, first = 0, second = 1, next, c;

printf("Enter the number of puk
");
scanf("%d",&n);

printf("First %d terms of fate sanka are :-
",n);

FOR ( c = 0 ; c < n ; c++ )
{
IF ( c <= 1 )
next = c;
else
{     //mlik man will save you FROM code vita
next = first + second;
first = second;
second = next;
}
printf("%d
",next);
}

RETURN 0;
}```

#### john

• Aug 7th, 2015

```Code#include <stdio.h>
#include <stdlib.h>

#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))

static int total_nodes;
// prints subset found
void printSubset(int A[], int size)
{
for(int i = 0; i < size; i++)
{
printf("%*d", 5, A[i]);
}

printf("
");
}

// inputs
// s            - set vector
// t            - tuplet vector
// s_size       - set size
// t_size       - tuplet size so far
// sum          - sum so far
// ite          - nodes count
// target_sum   - sum to be found
void subset_sum(int s[], int t[],
int s_size, int t_size,
int sum, int ite,
int const target_sum)
{
total_nodes++;
if( target_sum == sum )
{
// We found subset
printSubset(t, t_size);
// Exclude previously added item and consider next candidate
subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
return;
}
else
{
// generate nodes along the breadth
for( int i = ite; i < s_size; i++ )
{
t[t_size] = s[i];
// consider next level node (along depth)
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}

// Wrapper to print subsets that sum to target_sum
// input is weights vector and target_sum
void generateSubsets(int s[], int size, int target_sum)
{
int *tuplet_vector = (int *)malloc(size * sizeof(int));

subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);

free(tuplet_vector);
}

int main()
{
int weights[] = {10, 7, 5, 18, 12, 20, 15};
int size = ARRAYSIZE(weights);

generateSubsets(weights, size, 35);
printf("Nodes generated %d
", total_nodes);
return 0;
}
Run on IDE
The power of backtracking appears when we combine explicit and implicit constraints, and we stop generating nodes when these checks fail. We can improve the above algorithm by strengthening the constraint checks and presorting the data. By sorting the initial array, we need not to consider rest of the array, once the sum so far is greater than target number. We can backtrack and check other possibilities.

Similarly, assume the array is presorted and we found one subset. We can generate next node excluding the present node only when inclusion of next node satisfies the constraints. Given below is optimized implementation (it prunes the subtree if it is not satisfying contraints).

#include <stdio.h>
#include <stdlib.h>

#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))

static int total_nodes;

// prints subset found
void printSubset(int A[], int size)
{
for(int i = 0; i < size; i++)
{
printf("%*d", 5, A[i]);
}

printf("
suls");
}

// qsort compare function
int comparator(const void *pLhs, const void *pRhs)
{
int *lhs = (int *)pLhs;
int *rhs = (int *)pRhs;

return *lhs > *rhs;
}

// inputs
// s            - set vector
// t            - tuplet vector
// s_size       - set size
// t_size       - tuplet size so far
// sum          - sum so far
// ite          - nodes count
// target_sum   - sum to be found
void subset_sum(int s[], int t[],
int s_size, int t_size,
int sum, int ite,
int const target_sum)
{
total_nodes++;

if( target_sum == sum )
{
// We found sum
printSubset(t, t_size);

// constraint check
if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )
{
// Exclude previous added item and consider next candidate
subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
}
return;
}
else
{
// constraint check
if( ite < s_size && sum + s[ite] <= target_sum )
{
// generate nodes along the breadth
for( int i = ite; i < s_size; i++ )
{
t[t_size] = s[i];

if( sum + s[i] <= target_sum )
{
// consider next level node (along depth)
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
}
}

// Wrapper that prints subsets that sum to target_sum
void generateSubsets(int s[], int size, int target_sum)
{
int *tuplet_vector = (int *)malloc(size * sizeof(int));

int total = 0;

// sort the set
qsort(s, size, sizeof(int), &comparator);

for( int i = 0; i < size; i++ )
{
total += s[i];
}

if( s[0] <= target_sum && total >= target_sum )
{  //mlikman will save you from code vita

subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);

}

free(tuplet_vector);
}

int main()
{
int weights[] = {15, 22, 14, 26, 32, 9, 16, 8};
int target = 53;

int size = ARRAYSIZE(weights);

generateSubsets(weights, size, target);

printf("pukss generated %d
", total_nodes);

return 0;
}```

#### SathishKumaar Profile Answers by SathishKumaar

• Aug 7th, 2015

```Code#include <stdio.h>

int main(void) {
int t;
scanf("%d",&t);
while(t--)
{
int n,b,k,l;
scanf("%d",&n);
b=n/10;
k=n%10;
if(k!=0)
{
printf("%d",b+1);
}
else
{
printf("%d",b+0);
}
}
return 0;
}
```

#### Ritobrata Choudhury

• Aug 7th, 2015

```Code#include<stdio.h>
int process(int num)
{
int k1=0,k2=0,num2=num;
while(num>0)
{
if(num%10==0)
{
k1=k1+num/10;
num=num%10;
}
else if(num%7==0)
{
k1=k1+num/7;
num=num%7;
}
else if(num%5==0)
{
k1=k1+num/5;
num=num%5;
}
else
{
k1=k1+num;
num=0;
}

}
while(num2>0)
{
if(num2>=10)
num2=num2-10;
else if(num2>=7)
num2=num2-7;
else if(num2>=5)
num2=num2-5;
else
num2=num2-1;
k2++;
}
if(k1>k2)
return k2;
else
return k1;
}
void main()
{
int a[1000];
int n,i,num;
//printf("Enter Number of test cases:--");
scanf("%d",&n);
for(i=0;i<n;i++)
{
//printf("Enter a number >0:--");
scanf("%d",&num);
a[i]=process(num);
}
for(i=0;i<n;i++)
{
printf("%d
",a[i]);
}

}
```

#### Bikash Choudhury

• Aug 27th, 2015

```Code#include<iostream>
using namespace std;
int TestCase(int Num);

int main()
{
int N,Num,c=0,i=0;

cin>>N;
for(i=0;i<N;i++)
{
cin>>Num;
c=TestCase(Num);
cout<<c<<endl;
}

return 0;
}

int TestCase(int Num)
{
int mod=Num%10,c=0;
switch(mod)
{
case 0 :c=(Num/10);break;
case 1 :c=(Num/10)+1;break;
case 2 :c=(Num/10)+2;break;
case 3 :c=(Num/10)+3;break;
case 4 :c=((Num-1)/10)+2;break;
case 5 :c=(Num/10)+1;break;
case 6 :c=(Num/10)+2;break;
case 7 :c=(Num/10)+1;break;
case 8 :c=(Num/10)+2;break;
case 9 :c=((Num+10)/10)+1;break;
default :break;
}
return c;
}```

#### lavanya

• Jul 19th, 2016

```Code#include<stdio.h>
int main()
{
int b,n,l;
scanf("%d",&n);
while(n>0)
{
scanf("%d",&l);
b=0;
while(l>0)
{
b++;
if(l>=10)
l=l-10;
else if(l>=7)
l=l-7;
else if(l>=5)
l=l-5;
else
l=l-1;
}
printf("%d
",b);
n--;
}
return 0;
}```

#### t3chn0tr0n

• Jun 26th, 2019

Here is a take in Python.
Hope this helps.

```Codedef get_bottles(demand):
l = []
bottles = [1, 5, 7, 10]
for b in bottles:
if demand % b is 0:
l.append(int(demand / b))
demand_left = demand
bottles_needed = 0
i = 3
while demand_left != 0:
bottle_size = bottles[i]
if i != 0:
bottles_needed += int(demand_left / bottle_size)
demand_left -= int(demand_left / bottle_size) * bottle_size

i -= 1
else:
bottles_needed += demand_left
demand_left = 0
l.append(bottles_needed)
print(min(l))

n = int(input().strip())
while n:
get_bottles(int(input().strip()))
n -= 1
```