NYOJ 456-邮票分你一半(01背包)_邮票 题解 01 背包-程序员宅基地

技术标签: ACM-01背包  

邮票分你一半

时间限制: 1000 ms  |  内存限制: 65535 KB
难度: 3


题目链接:点击打开链接

描述

      小珂最近收集了些邮票,他想把其中的一些给他的好朋友小明。每张邮票上都有分值,他们想把这些邮票分成两份,并且使这两份邮票的分值和相差最小(就是小珂得到的邮票分值和与小明的差值最小),现在每张邮票的分值已经知道了,他们已经分好了,你知道最后他们得到的邮票分值和相差多少吗?
输入
第一行只有一个整数m(m<=1000),表示测试数据组数。
接下来有一个整数n(n<=1000),表示邮票的张数。
然后有n个整数Vi(Vi<=100),表示第i张邮票的分值。
输出

输出差值,每组输出占一行。


样例输入
2
5
2 6 5 8 9
3
2 1 5


样例输出
0
2



今天开始刷01背包,总是忘记把dp数组置0,有和我出一样毛病的小伙伴要多多注意。。。。。。


分析:这道题和我上午在HD上刷的一道题很像,本题的背包容量是邮票的分值,因为要分为两份分值相差最小的,所以背包容量就是邮票的总分值sum/2,因为邮票的价值也是自身的分值,所以推出状态转移方程为:dp[j]=max(dp[j],dp[j-s[i]]+s[i])。



#include <iostream>
#include<stdio.h>
#include<cmath>
#include<string.h>
using namespace std;

int main()
{
    int sum,m,n,s[1010],dp[100010];
    scanf("%d",&m);
    while(m--)
    {
        sum=0;
        memset(dp,0,sizeof(dp));
        memset(s,0,sizeof(s));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&s[i]);
            sum+=s[i];
        }
        for(int i=0;i<n;i++)
        {
            for(int j=sum/2;j>=s[i];j--)
                dp[j]=max(dp[j],dp[j-s[i]]+s[i]);
        }
        printf("%d\n",sum-dp[sum/2]-dp[sum/2]);
    }
    return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lz161530245/article/details/77119946

智能推荐

浏览器中Javascript的运行机制-EvenLoop究竟是如何实现的_浏览器中的运行机制evenlop-程序员宅基地

文章浏览阅读96次。Javascript语言详解,第二篇 || 同时也是浏览器架构的第一篇简单的JavascriptJavascript是一门weird language。它在某些地方以某种方式运行着,但你就是无法完全、彻底理解它。对于C/C++/Java这样的静态/编译型语言(强类型语言),我们清楚它是由gcc通过编译将源代码转换为二进制代码,当运行程序的时候,连接器把程序从硬盘复制到内存中并且运行。即使是python这样的动态/解释型语言(弱类型语言),也拥有自己特定的解释器把源代码转换成字节码的中间形式,然后._浏览器中的运行机制evenlop

springboot redis druid 负载均衡 mysql集群_springboot连接mysql集群-程序员宅基地

文章浏览阅读1.3k次。springboot redis druid 负载均衡 mysql集群_springboot连接mysql集群

【paddlepaddle】《百度深度学习7日打卡营-Python小白逆袭AI大神》学习心得_for j in range(len(result))-程序员宅基地

文章浏览阅读271次。课程宣传先上:https://aistudio.baidu.com/aistudio/course/introduce/1224在参加这期训练营之前,了解过PaddlePaddle,但是没有深度去了解他,后面通过PaddlePaddle官网发现了AIStudio。就开始在AIStudio上学习相关的课程,也看到了很多往期的七天打卡营,自己认为自己不是一个学习比较自觉地人,所以一直想要参加打..._for j in range(len(result))

【Godot测试】【在Godot中添加VRM模型和VMD动画并播放】_vrm模型下载-程序员宅基地

文章浏览阅读1.8k次。如果没有,请看:https://www.bilibili.com/video/BV1PJ411i7hK。设置方法:https://www.bilibili.com/read/cv7517116。加载成功,你可以看到,除了舞蹈动画,还有物理模拟和表情动画,如果你的vmd包含表情的话!下载:https://github.com/EIRTeam/VMDMotionDemo。要问什么,那当然是作者插件发布日期推算出的版本号就是3.3.3或以下。这个插件运行效率不高,毕竟是GDScript,耐心等待就好了。_vrm模型下载

集成学习(随机森林,提升方法-Adaboosting、Boosting tree、GBDT)_随机森林是如何提升其学习能力的-程序员宅基地

文章浏览阅读995次。参考了统计学习方法,西瓜书,Machine Learnig with python做的总结,还包含自己用sklearn做的一些对比实验,原文是写在jupyter上的,这里是直接转为.md导过来的,所以格式有些问题,有些东西还待完善…参考的博客https://www.cnblogs.com/pinard/p/6140514.html,https://blog.csdn.net/qq_222385..._随机森林是如何提升其学习能力的

oracle 数据库问题解决_oracle ensure all statements can be reached-程序员宅基地

文章浏览阅读690次。ORA-12519: TNS:no appropriate service handler found 解决有时候连得上数据库,有时候又连不上.可能是数据库上当前的连接数目已经超过了它能够处理的最大值.select count(*) from v$process --当前的连接数select value from v$parameter where name = '_oracle ensure all statements can be reached

随便推点

zookeeper --java API基本操作-程序员宅基地

文章浏览阅读1.6k次。org.apache.zookeeper.ZookeeperZookeeper 是在Java中客户端主类,负责建立与zookeeper集群的会话,并提供方法进行操作。org.apache.zookeeper.WatcherWatcher接口表示一个标准的事件处理器,其定义了事件通知相关的逻辑,包含KeeperState和EventType两个枚举类,分别代表了通知状态和事件类型,同时定...

从别处转来的好文章----给程序员的-程序员宅基地

文章浏览阅读524次。展望未来,总结过去10年的程序员生涯,给程序员小弟弟小妹妹们的一些总结性忠告 走过的路,回忆起来是那么曲折,把自己的一些心得体会分享给程序员兄弟姐妹们,虽然时代在变化,但是很可能你也会走我已经做过的10年的路程,有些心得体会你可以借鉴一下,觉得说得有道理的你就接纳,觉得说得没道理的,你就抛弃,以下是我发自内心的,给大家的忠告,特别是针对那些小弟弟妹妹们。01. 自己的户口档案、养老保险

STS环境_sts 环境 太痛苦-程序员宅基地

文章浏览阅读230次。调默认UTF-8_sts 环境 太痛苦

高精度计算_高精度格式的计算结果是否一定比低精度格式更精确?-程序员宅基地

文章浏览阅读219次。什么是高精度计算?实际上高精度就是说参与运算的数据和运算结果的范围,超出标准数据类型能表示的数据大小范围的运算。这个时候,如果要得到正确的计算结果,显然不能依靠普通方法实现了。而要在普通运算原理的基础上,加以辅助算法来实现超大数据的计算。例如:求两个100位的数据的和,或者计算两个100位的数字乘积。这时就要用到高精度算法了。参考博文:高精度计算详解高精度计算..._高精度格式的计算结果是否一定比低精度格式更精确?

网络命令工具telnet和nc(netcat)检查端口_netcat和telnet-程序员宅基地

文章浏览阅读5.3k次。两者区别telnet可以实现的功能:连接服务器端口,并进行通信 登录远程telnet服务器,使用命令行对其进行控制nc可以实现的功能:监听服务器端口,并与客户端通信(最多只能接收一个客户端) 对指定服务器进行端口扫描 作为客户端连接到远程服务器进行通信windows10启用telnet选择控制面板中的程序Ubuntu中使用telnetnetstat -a | grep t..._netcat和telnet

HDFS(9)--hdfs的fsimage,edits,secondarynameNode_hdfs 生成fsimage-程序员宅基地

文章浏览阅读1.6k次,点赞7次,收藏2次。NameNode元数据解析(1)第一次启动namenode格式化后,创建fsimage和edits文件。如果不是第一次启动,直接加载edits和fsimage文件到内存。(2)客户端对元数据进行增删改的请求。(3)namenode记录操作日志,更新滚动日志。(4)namenode在内存中对数据进行增删改查。fsimage保存了最新的元数据检查点,在HDFS启动时加载fsim..._hdfs 生成fsimage