本文主要是介绍uva 10163 - Storage Keepers(01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：10163 - Storage Keepers
题目大意：给出m为仓库的数量， 给出n为有守夜人的数量， 然后给出n个数值，为对应守夜人应付的酬劳，每个守夜人的能力与他需要的酬劳是相等的，并且守夜人可以同时负责多个仓库的安全，不过这样子安全值就变为val[i]/k（val[i]表示第i个守夜人的能力值，k表示他负责的仓库数量， /为取整），先在要的出方案，使得所有仓库中安全值最低的那个仓库的安全值越高， 并且要使得酬劳越低。
解题思路：问题应该分成两个子问题来求解，先求安全值最大为多少，然后通过求出的安全值去求解酬劳的最优方案。
1、dp[j] = max(dp[j], min(dp[j - k], val[i] / k)), 可以将max中的两个数值看成是两个方案，是否用min中的方案取代原先的方案。 而min则为该方案中的安全值最低值。（dp[i] 表示保证了i个仓库的安全后的安全值最低值）
2、dp[j] = min(dp[j], dp[j - k] + val[i]), dp[j]表示保证j个仓库的安全值大于ans（第一步求出的最优解）时的花费最小值。
#include <stdio.h>
#include <string.h>
const int N = 1005;
const int M = 105;
const int MAX = 1 << 30;
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }int n, m, ans, dp[N], val[M];int solve() {memset(dp, 0, sizeof(dp));dp[0] = 1 << 30;for (int i = 0; i < n; i++) {for (int j = m; j >= 0; j--) {for (int k = 1; k <= j && k <= val[i]; k++)dp[j] = max(dp[j], min(dp[j - k], val[i] / k));}}return dp[m];
}int find() {if(ans == 0) return 0;for (int i = 1; i <= m; i++)dp[i] = MAX;dp[0] = 0;for (int i = 0; i < n; i++) {for (int j = m; j >= 0; j--) {for (int k = min(j, val[i] / ans); k > 0; k--)dp[j] = min(dp[j], dp[j - k] + val[i]);}}return dp[m];
}int main() {while (scanf("%d%d", &m, &n), n || m) {for (int i = 0; i < n; i++)scanf("%d", &val[i]);ans = solve();printf("%d %d\n", ans, find());}return 0;
}
这篇关于uva 10163 - Storage Keepers(01背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
