ACM刷题之路（二十二）多重背包转01背包 HDU 1171

我会带着你远行 2024-02-19 20:41 53阅读 0赞

[题目链接：传送门][Link 1]

<table> 
 <tbody> 
 <tr> 
 <td> 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&lt;N&lt;1000) kinds of facilities (different value, different kinds). &nbsp; &nbsp; Input Input contains multiple test cases. Each test case starts with a number N (0 &lt; N &lt;= 50 -- the total number of different facilities). The next N lines contain an integer V (0&lt;V&lt;=50 --value of facility) and an integer M (0&lt;M&lt;=100 --corresponding number of the facilities) each. You can assume that all V are different. A test case starting with a negative integer terminates input and this test case is not to be processed. &nbsp; &nbsp; 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. &nbsp; &nbsp; Sample Input <pre><code>&nbsp;</code></pre> 2 10 1 20 1 3 10 1 20 2 30 1 -1 &nbsp; &nbsp; Sample Output <pre><code>&nbsp;</code></pre> 20 10 40 40 </td> 
 </tr> 
 </tbody> 
</table>

**题意：**

样例：

10 1

20 1

意思是**两种物品，质量为10的物品有一个，质量为20的物品有一个，求如何分使得最大程度的两等分**？

答案当然是 ： **20 10** （题目规定大的放前面）

10 1

20 2

30 1

意思是**三种物品，质量为10的物品有一个，质量为20的物品有两个，，质量为30的物品有一个，求如何分使得最大程度的两等分**？

答案当然是 ： **40 40** 即20 20放一起 、10 30 放一起即可

**分析：**本题我采用**多重背包转01背包**的做法，把输入的物品质量放入a数组，如果物品数量大于1，就放多次，当然可以二进制优化，但在本题中不优化也可以AC。

**另外注意判断输入结束必须是t<0 ，而不是t==-1！！！**

当然下面就是01背包的模板

for i=1..N
        for v=V..0
            f[v]=max{f[v],f[v-c[i]]+w[i]};

在本题中，**第一层遍历物品的个数N，第二层遍历背包容量sum/2**，状态转移方程一套就可以了。

注意dp数组的初始化，还有输出大的放前面即可。

#include<iostream>
 #include<algorithm>
 #include<cstring>
 using namespace std;
 int a[5002];
 int dp[500002];
 int maxx(int x, int y) {
 	return x > y ? x : y;
 }
 int main()
 {
 	int t;
 	while (~scanf_s("%d", &t) && t >= 0) {
 		int len = 0;
 		int sum = 0;
 		while (t--) {
 			int x, y;
 			scanf_s("%d%d", &x, &y);
 			sum += x * y;
 			while (y--) {
 				a[len++] = x;
 			}
 		}
 		int summ = sum;
 		sum /= 2;
 		memset(dp, 0, sizeof(dp));
 		for (int i = 0; i < len; i++) {
 			for (int j = sum; j >= a[i]; j--) {
 				dp[j] = maxx(dp[j], dp[j - a[i]] + a[i]);
 			}
 		}
 		printf("%d %d\n", summ - dp[sum], dp[sum]);
 	}
 	return 0;
 }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1171