Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1104
Randy Company has N (1 ≤ N ≤ 100) storages. Company wants some men to keep them safe. Now there are M (1 ≤ M ≤ 30) men asking for the job. Company will choose several from them. Randy Company employs men following these rules: 1. Each keeper has a number Pi (1 ≤ Pi ≤ 1000) , which stands for their ability. 2. All storages are the same as each other. 3. A storage can only be lookd after by one keeper. But a keeper can look after several storages. If a keeper’s ability number is Pi , and he looks after K storages, each storage that he looks after has a safe number Uj = Pi ÷ K.(Note: Uj , Pi and K are all integers). The storage which is looked after by nobody will get a number 0. 4. If all the storages is at least given to a man, company will get a safe line L = minUj 5. Every month Randy Company will give each employed keeper a wage according to his ability number. That means, if a keeper’s ability number is Pi , he will get Pi dollars every month. The total money company will pay the keepers every month is Y dollars. Now Randy Company gives you a list that contains all information about N, M, P, your task is give company a best choice of the keepers to make the company pay the least money under the condition that the safe line L is the highest. Input The input file contains several scenarios. Each of them consists of 2 lines: The first line consists of two numbers (N and M), the second line consists of M numbers, meaning Pi (i = 1..M). There is only one space between two border numbers. The input file is ended with N = 0 and M = 0. Output For each scenario, print a line containing two numbers L(max) and Y (min). There should be a space between them.
Sample Input 2 1 7 1 2 10 9 2 5 10 8 6 4 1 5 4 1 1 1 1 0 0
Sample Output 3 7 10 10 8 18 0 0
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
int T[31][102];
int Y[31][102];
int p[31];
while(scanf("%d %d", &n, &m), n+m) {
for(int i=0;i < m;i++)
scanf("%d", p+i);
memset(T, 0, sizeof T);
memset(Y, 127, sizeof Y);
// find max T - safeline of all storage
for(int i=0;i < m;i++) { // foreach keeper
T[i][0] = 1e7;
for(int j=0;j < =n;j++) { // foreach sub-problem size, smaller problems first
T[i+1][j] = max(T[i+1][j], T[i][j]); // safeline excluding keeper i (0 storage)
for(int k=1;j+k < =n;k++) { // number of storages handled by keeper i
int val = min(T[i][j], p[i]/k); // min safeline including keeper i
T[i+1][j+k] = max(T[i+1][j+k], val);
}
}
}
// find min Y
int res = T[m][n];
for(int i=0;i < m;i++) {
Y[i][0] = 0;
for(int j=0;j < =n;j++) {
if(T[i+1][j] >= res)
Y[i+1][j] = min(Y[i+1][j], Y[i][j]);
for(int k=1;j+k<=n;k++) {
int val = min(T[i][j], p[i]/k>;
if(val >= res) // if same T, update Y
Y[i+1][j+k] = min(Y[i+1][j+k], Y[i][j]+p[i]);
}
}
}
if(res == 0) Y[m][n] = 0;
printf("%d %d\n", res, Y[m][n]);
}
}Input
7
1 2
10 9
2 5
10 8 6 4 1
5 4
1 1 1 1
0 0
Output
10 10
8 18
0 0
Demonstration
UVA Online Judge solution - 10163-Storage Keepers - UVA Online Judge solution in C,C++,Java