首页 > 代码库 > [HDOJ 1171] Big Event in HDU 【完全背包】
[HDOJ 1171] Big Event in HDU 【完全背包】
题目链接：HDOJ - 1171
题目大意
有 n 种物品，每种物品有一个大小和数量。要求将所有的物品分成两部分，使两部分的总大小尽量接近。
题目分析
令 Sum 为所有物品的大小总和。那么就是用给定的物品做完全背包，背包容量为 (Sum / 2) ，得到的结果是较小的一部分的大小。
完全背包问题可以使用单调队列优化，O(nm) 。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 1000 + 5, MaxM = 250000 + 5;int n, Sum, Sum1, A, B, Head1, Tail1, Head2, Tail2;int V[MaxN], Num[MaxN], Q1[MaxM], Q2[MaxM], f[MaxM];int main() { while (true) { scanf("%d", &n); if (n < 0) break; Sum = 0; for (int i = 1; i <= n; ++i) { scanf("%d%d", &V[i], &Num[i]); Sum += V[i] * Num[i]; } Sum1 = Sum >> 1; for (int i = 0; i <= Sum1; ++i) f[i] = 0; int Ni, Vi, t; for (int i = 1; i <= n; ++i) { Ni = Num[i]; Vi = V[i]; for (int j = 0; j < Vi; ++j) { Head1 = Tail1 = 0; Head2 = Tail2 = 0; for (int k = j, Cnt = 0; k <= Sum1; k += Vi, ++Cnt) { if (Tail1 - Head1 == Ni + 1) { if (Q2[Head2 + 1] == Q1[Head1 + 1]) ++Head2; ++Head1; } t = f[k] - Cnt * Vi; Q1[++Tail1] = t; while (Head2 < Tail2 && Q2[Tail2] < t) --Tail2; Q2[++Tail2] = t; f[k] = Q2[Head2 + 1] + Cnt * Vi; } } } B = f[Sum1]; A = Sum - B; printf("%d %d\n", A, B); } return 0;}
[HDOJ 1171] Big Event in HDU 【完全背包】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。