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;

}
  

?

?

UVA 10163 Storage Keepers(dp + 背包)