2
10 1
20 1
3
10 1 
20 2
30 1
-1

20 10
40 40

題目大意：有n種物品，價值為vi的有mi個，現在要買兩份，要求第一份物品總價值大於等於第二份，且兩份物品總價值的差最小

題目分析：多重背包問題，遞減枚舉價值，一旦當前價值超過了總價值的一半，計算差值取最小

#include 
int m[55], v[55];

int main()
{
    int n;
    while(scanf(%d, &n) != EOF && n > 0)
    {
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            scanf(%d %d, &v[i], &m[i]);
            sum += v[i] * m[i];
        }
        int mi = sum, ans = v[0];
        for(int i = 0; i < n; i++)
            for(int j = sum; j >= v[i]; j--)
                for(int k = 0; k <= m[i]; k++)
                    if(j >= k * v[i])
                        if(k && j % (k * v[i]) == 0 && j * 2 >= sum && 2 * j - sum < mi)
                        {
                            mi = 2 * j - sum;
                            ans = j;
                        }
        printf(%d %d
, ans, sum - ans);
    }
}