| Problem C.Storage Keepers |
Background
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 div 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=min Uj
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
题意：有m个仓库， n个小伙伴，每个小伙伴有个能力值p，要这些小伙伴去守护仓库，每个小伙伴的雇佣金是p，每个小伙伴看守的仓库安全值为p/k(每个小伙伴看守仓库数)。仓库的安全值为所有仓库中，安全值最小的仓库的安全值。
要求出最大安全值和最大安全值下的最小开销。
思路： 背包， 首先是第一个问题，我们把每个小伙伴看成物品，要看守的仓库数看成背包容量，每个小伙伴看守的仓库数为k，价值为p[i]/k。 状态转移方程为dp[j] = max(dp[j], min(dp[j - k], p[i]/k).。
然后是第二个问题。在第一个问题求出的最大安全值maxx下，求最小价值，依然是背包，k表示每个小伙伴看守的仓库数，状态转移方程为dp[j] = min(dp[j], dp[j - k] + p[i]);
代码：
#include <stdio.h>
#include <string.h> const int INF = 1 << 30;
int n, m, p[105], i, j, k, dp[1005], maxx, minn; int max(int a, int b) {
return a > b ? a : b;
} int min(int a, int b) {
return a < b ? a : b;
} int main() {
while (~scanf("%d%d", &m, &n) && m || n) {
memset(dp, 0, sizeof(dp));
dp[0] = INF;
for (i = 0; i < n; i ++)
scanf("%d", &p[i]);
for (i = 0; i < n; i ++) {
for (j = m; j >= 0; j --) {
for (k = 1; k <= p[i] && k <= j; k ++) {
dp[j] = max(dp[j], min(dp[j - k], p[i] / k));
}
}
}
maxx = dp[m];
if (maxx == 0) {
printf("0 0\n");
continue;
}
for (i = 1; i <= m; i ++)
dp[i] = INF;
dp[0] = 0;
for (i = 0; i < n; i ++)
for (j = m; j >= 0; j --)
for (k = min(j, p[i]/maxx); k > 0; k --) {
dp[j] = min(dp[j], dp[j - k] + p[i]);
}
printf("%d %d\n", maxx, dp[m]);
}
return 0;
}