hdu 1171 Big Event in HDU 费用可行性背包 dp

题意

一个学院分成了两个学院，于是他们要分一些公共设备。总共有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;
}