Description
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 the best way to fill this N-liter empty container using the provided smaller containers. By ‘best’, we mean that the total number of used containers should be as small as possible. For example, assume that we have containers in 1, 5, and 10 liters. To get the 17 liters of water, we need 2 containers of 1 liter, 1 container of 5 liters, and 1 container of 10 liters. Another example: assume that we have containers in 1, 5, 10 and 50 liters. To get the 57 liters of water, we need 1 container of 50 liters, 1 container of 5 liters, and 2 containers of 1 liter. Note that, to avoid water wastage, if you choose to use a container, all the water in this container should be poured.
The following is an excerpt of incomplete code:
|
#include #define MAXNV 5 int DONE = 0; int liters[MAXNV]; int numbers[MAXNV]; void show(int nv); void filling(int amount, int cur, int nv); int j=0; int water; int min=100; int min_numbers[MAXNV]={0}; int main(void) { int nv, i;
scanf("%d", &nv); for (i=0; i scanf("%d", &liters[i]); } scanf("%d", &water); filling(water, 0, nv); for(i=0;i numbers[i]=min_numbers[i]; show(nv); return 0; } void show(int nv) { int i; printf("(%d", numbers[0]); for (i=1; i printf(",%d", numbers[i]); } printf(")\n"); } void filling(int amount, int cur, int nv) { int i,j,count_numbers=0; if(cur if(amount==0){ for(i=0;i count_numbers=count_numbers+numbers[i]; if(count_numbers min=count_numbers; for(i=0;i min_numbers[i]=numbers[i]; } return 0; } else if(amount>=liters[cur]){ /*your code*/ } else{ /*your code*/ } } } |
Input
The input contains three lines. The first line contains an integer N (0
Output
The result can be displayed by calling the function show().
Only the best way to fill the empty container should be displayed.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a set of 
elements, the problem is to print all possible permutations of this set. For example, if the set is (1,2,3), then the set of permutations is {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)}.
Looking at the case of four elements (1,2,3,4). The answer can be constructed by writing
1. ‘1’ followed by all the permutations of (2,3,4)
2. ‘2’ followed by all the permutations of (1,3,4)
3. ‘3’ followed by all the permutations of (1,2,4)
4. ‘4’ followed by all the permutations of (1,2,3)
A recursive method to implement the above idea is as follows:
Consider the case of (1,2,3,4), that is, n=4.
1. Place the set elements in a global array, and set the position index “k” as 0.
2. Use a for-loop to “swap” (or exchange) the 1st element with the 1st element, the 2nd element, the 3rd element, and the 4th element, respectively.
l In each loop-iteration:
i. increment the position index “k” by 1 (for considering only the remaining elements in the following recursive call);
ii. use the updated k to recursively call your permutation function;
iii. note that because you use a global array, remember to swap back the two elements after the iteration.
3. In a recursive-call path, when k reaches n, it means that you get a possible permutation.
You can use the following incomplete code to solve this problem.
|
#include
void Show(int n); void Swap(int k, int i); void Perm(int k, int n); char list[9]={'1','2','3','4','5','6','7','8','9'};
int main(void) { int num; scanf("%d",&num); Perm(0,num); return 0; }
void Show(int n) { int i; printf("(%c", list[0]); for (i=1; i printf(",%c", list[i]); } printf(")\n"); }
void Swap(int k, int i) { char temp; /*your code*/ }
void Perm(int k, int n) { int i; if(k==n) { /*print your answer*/ } else { for(i=k; i { /*your code*/ } } } |
Input
The decimal number n that represents the number of elements in the set.
(
)
Output
In the output you should print all the permutations.
Be sure to add a newline character '\n' at the end of each line.