HDU 1171(01背包)

时间:2022-10-20 14:04:48

Big Event in HDU

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 29234    Accepted Submission(s): 10275

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<N<1000) kinds of facilities (different value, different kinds).
 
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<V<=50 --value of facility) and an integer M (0<M<=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.
 
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
 
Author
lcy
                                                                          HDU 1171(01背包)
可坑死我了,一直tle,我还以为算法错了呢,原来是输入要求N>0,否则停止,我还以为等于-1停止呢。。
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define _cle(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define repd(i, a, b) for(int i = b; i >= a; i--)
#define sfi(n) scanf("%d", &n)
#define sfl(n) scanf("%I64d", &n)
#define pfi(n) printf("%d\n", n)
#define pfl(n) printf("%I64d\n", n)
#define MAXN 5000005
int dp[];
int v[];
int main()
{
int n;
while(sfi(n), n > )
{
int sum = ;
_cle(dp, );
int tot = ;
int x, y;
repu(i, , n)
{
sfi(x), sfi(y);
repu(j, , y)
v[tot++] = x;
sum += x * y;
}
int m = sum / ; repu(i, , tot)
for(int k = m; k >= v[i]; k--)
{
dp[k] = max(dp[k], dp[k - v[i]] + v[i]);
}
printf("%d %d\n", sum - dp[m], dp[m]);
}
return ;
}

HDU 1171(01背包)的更多相关文章

  1. HDU 1171 01背包

    http://acm.hdu.edu.cn/showproblem.php?pid=1171 基础的01背包,求出总值sum,背包体积即为sum/2 #include<stdio.h> # ...

  2. hdu 1203 01背包 I need a offer

    hdu 1203  01背包  I need a offer 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1203 题目大意:给你每个学校得到offe ...

  3. HDU 1171 Big Event in HDU【01背包&sol;求两堆数分别求和以后的差最小】

    Big Event in HDU Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) T ...

  4. HDU 1171 Big Event in HDU【01背包】

    题意:给出n个物品的价值和数目,将这一堆物品分给A,B,问怎样分使得两者的价值最接近,且A的要多于B 第一次做的时候,没有思路---@_@ 因为需要A,B两者最后的价值尽可能接近,那么就可以将背包的容 ...

  5. hdu 2955 01背包

    http://acm.hdu.edu.cn/showproblem.php?pid=2955 如果认为:1-P是背包的容量,n是物品的个数,sum是所有物品的总价值,条件就是装入背包的物品的体积和不能 ...

  6. &lbrack;HDOJ1171&rsqb;Big Event in HDU(01背包)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1171 许多有价值的物品,有重复.问如何将他们分成两堆,使两堆价值之差最小. 对价值求和,转换成01背包 ...

  7. hdoj1171 Big Event in HDU(01背包 &vert;&vert; 多重背包)

    题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1171 题意 老师有一个属性:价值(value).在学院里的老师共有n种价值,每一种价值value对应着 ...

  8. hdu 1864 01背包 最大报销额

    http://acm.hdu.edu.cn/showproblem.php?pid=1864 New~ 欢迎“热爱编程”的高考少年——报考杭州电子科技大学计算机学院关于2015年杭电ACM暑期集训队的 ...

  9. Big Event in HDU(HDU 1171 多重背包)

    Big Event in HDU Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others ...

随机推荐

  1. PHP获取二维数组中的指定若干列【同array&lowbar;column】

    PHP5.3以上  用到了array_map 使用匿名函数进行处理 代码: <?php function array_col($arr = array(), $idx = 0, $newidx ...

  2. NET IL命令查询器

    最近研究了一下IL代码,闲来无事,开发一个小工具,供大家使用.编程.破解,手头必备工具. 模糊搜索,可以把相关的命令都列出来.选中行,可以提示指令说明. 如果指令不全,可以增加指令及说明. CSDN下 ...

  3. MD5编码工具类 MD5Code&period;java

    代码如下: package com.util; /** * MD5编码工具类 * http://www.cnblogs.com/sosoft/ */ public class MD5Code { st ...

  4. day4----json的简单实用

    json官方说明参见:http://json.org/ Python操作json的标准api库参考:http://docs.python.org/library/json.html 重要函数 编码:把 ...

  5. Sublime Text 编辑器

    1.从http://www.sublimetext.com/2 下载Sublime Text 2编辑器. 2.安装Package Control 管理器,用于管理和安装插件包. 下载地址:https: ...

  6. 关于SubclassWindow&lpar;&rpar;和SubclassDlgItem

    msdn上的解析 CWnd::SubclassWindowBOOL SubclassWindow( HWND hWnd ); Return Value Nonzero if the function ...

  7. java线程池的创建使用

    利用java的多线程编程可以大大的提高系统的并发运行效率,线程越多并发执行的任务就越多,但是并不意味着效率会一直提高,相反会得到适得其反的效果. java中的多线程编程一共有三种方法: 继承Threa ...

  8. 手动调用run方法和普通方法调用没有区别

    手动调用run方法和普通方法调用没有区别

  9. 【测试工具】Macaca 自动遍历器 NoSmoke

    Macaca 提供的基础能力上研发出了一套多端深度遍历爬虫工具. 希望可以最大化减少UI 测试脚本的编写涵盖以下功能点: 支持iOS, Android,PC-Web 三个平台的自动化测试 同时可以通过 ...

  10. 蜗牛慢慢爬 LeetCode 16&period; 3Sum Closest &lbrack;Difficulty&colon; Medium&rsqb;

    题目 Given an array S of n integers, find three integers in S such that the sum is closest to a given ...