程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1171 Big Event in HDU (多重背包變形)

HDU 1171 Big Event in HDU (多重背包變形)

編輯:C++入門知識

HDU 1171 Big Event in HDU (多重背包變形)


 

Big Event in HDU

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 27961 Accepted Submission(s): 9847

Problem Description Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0
Input Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number of different facilities). The next N lines contain an integer V (0 A test case starting with a negative integer terminates input and this test case is not to be processed.

Output For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.

Sample Input
2
10 1
20 1
3
10 1 
20 2
30 1
-1

Sample Output
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);
    }
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved