题意
一个学院分成了两个学院,于是他们要分一些公共设备。总共有n
种设备,每种设备的价值v[i]
和数量m[i]
,要求分配的时候尽可能的让两个学院分到的价值接近。并且保证第一个学院分得的价值不小于第二个学院。求最佳分配结果。
思路
要尽可能的平均分配,就是尽可能地用这些设备凑成总价值的一半。而只需要知道那种价值能否凑出来。
code
#include <bits/stdc++.h>
using namespace std;
int n;
int v[55], m[55];
int sum, poi;
int dp[250000 + 5];
int use[250000 + 5];
int main () {
while (scanf ("%d", &n) != EOF && n >= 0) {
sum = 0;
for (int i=1; i<=n; i++) {
scanf ("%d %d", &v[i], &m[i]);
sum += v[i] * m[i];
}
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i=1; i<=n; i++) {
memset (use, 0, sizeof (use));
for (int j=v[i]; j<=sum/2; j++){
if (dp[j] == 0 && dp[j-v[i]] == 1 && use[j-v[i]] + 1 <= m[i]) {
dp[j] = 1;
use[j] = use[j-v[i]] + 1;
}
}
}
for (int i=sum/2; i>=0; i--) {
if (dp[i] == 1) {
poi = i;
break;
}
}
printf ("%d %d\n", sum - poi, poi);
}
return 0;
}