NYOJ 456-邮票分你一半（01背包）_nyoj 456 邮票分你一半-程序员宅基地

邮票分你一半

时间限制： 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;
}

本文链接：https://blog.csdn.net/lz161530245/article/details/77119946

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

ping——判断两个设备是否在同一个局域网下_怎么判断会否同一局域网通信-程序员宅基地

文章浏览阅读1w次。有时需要检查两个设备（有线/无线）是否在同一个局域网下面怎么操作呢？一、windows下1、在搜索输入cmd，打开命令行编辑器2、输入ipconfig查看本电脑的IP地址3、查另一台设备的ip地址为10.138.223.954、在本电脑命令行输入ping 10.138.223.955、显示结果如下（一个无线一个有线）表示设备在同一个局域网内二、Linux下树莓派ping通指定ip地址后，会一直循环，如果想要退出ping循环，则摁键盘组合件：Ctrl+Z。..._怎么判断会否同一局域网通信

js签名效果的base64编码图片上传到后端服务器遇到的一些问题_js手写签名不能上传的问题-程序员宅基地

文章浏览阅读827次。签名demo:https://github.com/xuyongsky123/canvasSignature(侵删)作出适当修改放入我的网站里面问题一：在移动端签字时页面会被拖拽解决：绑定canvas容器touchmove//阻止签名时页面拖拽 document.getElementById("signatureTab").addEventListener('touchmove', function (e) { e.preventDefault(); ._js手写签名不能上传的问题

一个强大易用的java bean之间属性复制框架--Dozer介绍-程序员宅基地

文章浏览阅读206次。2019独角兽企业重金招聘Python工程师标准>>> ..._java bean拷贝新框架

mysql 主从复制日志_mysql基于日志的主从复制详解-程序员宅基地

文章浏览阅读134次。总有人问我会不会读写分离，我有时真的不知道怎么回答，这么滴吧，技术本身不难你，难的是咱们能不能遇得到这么大的项目。如果是真有这么大项目，光读写分离这个事肯定不是一两个人在搞，应该是多人协作的。相关学习推荐：mysql视频教程所以呢！我没搞过。但是……不能做实验环境吗？(一个尴尬的笑容)我从找文档资料到实验落地，一共花了3天时间(因为不是全天都在围绕着这个事情哇)。基本搞定，就是说，如果有人问我会..._mysql主从复制主存在多个日志文件

lecode/每日一题/2020/7/30_lecode至少有多少个粒子特性发生变换-程序员宅基地

文章浏览阅读164次。删除排序数组中的重复项给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。示例 1:给定数组 nums = [1,1,2],函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。你不需要考虑数组中超出新长度后面的元素。示例 2:给定 nums = [0,0,1,1,1,2,2,3,3,4],函数应该返回新的长度 5, _lecode至少有多少个粒子特性发生变换

部分google hacking的搜索内容-程序员宅基地

文章浏览阅读5.4w次。inurl:index.php?id=inurl:trainers.php?id=inurl:buy.php?category=inurl:article.php?ID=inurl:play_old.php?id=inurl:declaration_more.