Suppose that you have an infinite number of containers with different sizes, already filled with water. Given another empty container with size N liters, you need to find out all the possible methods to fill this N-liter empty container using the provided smaller containers. Note that, to avoid water wastage, if you choose to use a container, all the water in this container should be poured.
For example, assume that we have containers in 1, 5, and 10 liters. To get the 17 liters of water, all the possible methods are listed below:
You will be provided with the following sample code, and asked to implement function "filling".
#include <stdio.h>
#define MAXNC 5
int liters[MAXNC];
int solution[MAXNC];
void showResult(int n) {
int i;
printf("(%d", solution[0]);
for (i=1; i<n ;i++) {
printf(",%d", solution[i]);
}
printf(")\n");
return;
}
void filling(int amount, int cur, int n) {
/*Your code*/
}
int main(void) {
int n, i;
int water;
scanf("%d", &n);
for (i=0; i<n ;i++) {
scanf("%d", &liters[i]);
}
scanf("%d", &water);
filling(water, 0, n);
return 0;
}
The input contains three lines.
The first line contains an integer M (0<M<=5) which represents the number of different size containers.
The second line contains M numbers, S1 ,S2 , …, SM. Si represents the size of the i-th container. Note that these M numbers are in decreasing order.
The third line contains an integer N (0<N<100) which represents the size of the empty container.
Display all the possible methods to fill the empty container. Each line represents a method in the format “(C1,C2,…,CM)”, where Cirepresents the number of the size Si container.