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<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
 
题目链接:http://acm.hdu.edu.cn/showproblem.php?

pid=1171


题目大意:有n种物品,价值为vi的有mi个,如今要买两份。要求第一份物品总价值大于等于第二份,且两份物品总价值的差最小


题目分析:多重背包问题。递减枚举价值,一旦当前价值超过了总价值的一半,计算差值取最小


#include <cstdio>
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\n", ans, sum - ans);
    }
}





本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5379914.html,如需转载请自行联系原作者  

相关文章
|
域名解析 网络协议 Linux
curl 和 wget 的使用和区别
curl 和 wget 的使用和区别
427 0
|
前端开发 Java
javaweb实训第四天上午——员工管理系统-JavaBean&EL&JSTL&MVC思想(1)
1.课程介绍 项目需求分析; (了解) JavaBean; (掌握) El表达式; (掌握) JSTL标签; (掌握) MVC思想; (掌握)
131 0
|
SQL 数据库
|
9月前
|
前端开发 安全 数据挖掘
在电商行业中 API 是什么意思?
在电商行业飞速发展的当下,API(应用程序编程接口)作为支撑各类应用高效运转的关键技术,扮演着不可或缺的角色。无论是商品展示、订单处理还是物流跟踪,API 都是连接不同系统和服务的桥梁。本文将详细阐述电商行业中 API 的概念、类型(如 RESTful、SOAP 和 GraphQL)、应用场景(如商品管理、订单处理、物流跟踪和数据分析),并通过代码示例展示其实际应用。掌握 API 知识,有助于电商从业者推动业务创新,在竞争中占据优势。
303 12
|
12月前
|
SQL 存储 人工智能
OceanBase CTO杨传辉谈AI时代下数据库技术的创新演进路径!
在「DATA+AI」见解论坛上,OceanBase CTO杨传辉先生分享了AI与数据库技术融合的最新进展。他探讨了AI如何助力数据库技术演进,并介绍了OceanBase一体化数据库的创新。OceanBase通过单机分布式一体化架构,实现了从小规模到大规模的无缝扩展,具备高可用性和高效的数据处理能力。此外,OceanBase还实现了交易处理、分析和AI的一体化,大幅提升了系统的灵活性和性能。杨传辉强调,OceanBase的目标是成为一套能满足80%工作负载需求的系统,推动AI技术在各行各业的广泛应用。关注我们,深入了解AI与大数据的未来!
OceanBase CTO杨传辉谈AI时代下数据库技术的创新演进路径!
|
机器学习/深度学习 人工智能 自然语言处理
科普神文,一次性讲透AI大模型的核心概念
令牌,向量,嵌入,注意力,这些AI大模型名词是否一直让你感觉熟悉又陌生,如果答案肯定的话,那么朋友,今天这篇科普神文不容错过。我将结合大量示例及可视化的图形手段,为你由浅入深一次性讲透AI大模型的核心概念。本文转载至:https://baijiahao.baidu.com/s?id=1779925030313909037&wfr=spider&for=pc。确实是一篇很不错的文,很好的解释了大模型底层的一些基本概念,对于我这种AI新手非常友好哈哈哈
科普神文,一次性讲透AI大模型的核心概念
|
12月前
|
算法 数据可视化 Python
使用 Python 模拟蒙特卡洛实验
使用 Python 模拟蒙特卡洛实验
301 1
|
IDE 前端开发 开发工具
怎么在isort Python 代码中的导入语句进行排序和格式化
`isort` 是一个Python工具,用于自动排序和格式化代码中的导入语句,提高代码整洁度和可读性。它支持自动排序、保留空白和注释、自定义排序规则、与多种编辑器集成以及命令行使用。安装`isort`可通过`pip install isort`,使用时可直接在Python代码中导入或通过命令行处理文件。示例展示了如何在代码中使用`isort`进行导入排序,包括基本排序、自定义设置和处理多个文件。`isort`适用于标准库、第三方库和自定义模块的导入排序,还可忽略特定导入,并能与IDE和编辑器插件集成,提升开发效率。
198 2
|
监控 安全 数据安全/隐私保护
云端智控:智能监控系统的新时代
云上智能监控系统作为一项重要的技术手段,在保障公共安全、提升生产效率等方面发挥着越来越重要的作用。尽管还面临着一些挑战,但随着技术的不断进步和完善,智能监控系统将更加智能化、人性化。未来,我们可以期待更多的技术创新和应用模式出现,让智能监控系统成为智慧城市中不可或缺的一部分。
|
Java 关系型数据库 数据库连接
【C 言专栏】C 语言与数据库的连接与操作
【5月更文挑战第2天】本文探讨了C语言如何连接和操作数据库,介绍了数据库连接的基本原理,如通过ODBC、JDBC或原生接口与数据库交互。文章详细阐述了使用ODBC连接的步骤,并列举了C语言在数据库操作中的常见任务,强调了错误处理、数据类型匹配和性能优化的重要性。通过实际案例,展示了在学生信息管理系统中应用C语言与数据库交互的过程。本文旨在帮助读者更好地理解和应用C语言进行数据库管理。
373 2