51nod 1007 正整数分组（类01背包问题）

Love The Way You Lie 2022-08-20 12:29 147阅读 0赞

将一堆正整数分为2组，要求2组的和相差最小。

例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。

这道题就是要求在n个数字里面选出一些数，计算出这些数字的和，然后在计算出剩下数字的和然后求出这两个和的差的最小值，我们可以看出，关键就是怎么样选这些数字。

选数字，这就和01背包有点像了。我们可以先计算出这些数字的总和，然后将背包的容量看成是这个和的一半，然后从这些数字里面选出一些来看这个背包最多能装多少就可以了。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 10005;
    int dp[maxn];
    int a[105];
    
    int main()
    {
        int n,v,sum ;
        while(scanf("%d",&n)!=EOF)
        {
            sum = 0 ;
            for(int i = 0 ; i < n ; i++)
            {
                scanf("%d",&a[i]);
                sum+=a[i];
            }
            v=sum/2;
            memset(dp,0,sizeof(dp));
            for(int i = 0 ; i < n ; i++)
            {
                for(int j = v ; j >= a[i] ; j--)
                {
                    dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
                }
            }
            printf("%d\n",sum-2*dp[v]);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 51Nod 1086 背包问题 V2(二进制多重背包)

知识点：Cn=1+2+4+8+.....+ 2^(m-2)+t。我们可以检验，在\[1,Cn\]中任意的数我们都可以在这个序列中找到若干数相加得到。 [1086 背包问题

一时失言乱红尘/ 2024年02月17日 19:19/ 0 赞/ 34 阅读

相关背包问题 AcWing 9. 分组背包问题

背包问题 AcWing 9. 分组背包问题原题链接 [AcWing 9. 分组背包问题][AcWing 9.] 算法标签背包问题 DP 思路 !

桃扇骨/ 2023年09月28日 13:34/ 0 赞/ 45 阅读

相关 51nod 1007 正整数分组（类01背包问题）

将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。这道题就是要

Love The Way You Lie/ 2022年08月20日 12:29/ 0 赞/ 148 阅读

相关 51nod 1101 找零问题 dp （01背包问题）

N元钱换为零钱，有多少不同的换法？币值包括1 2 5分，1 2 5角，1 2 5 10 20 50 100元。例如：5分钱换为零钱，有以下4种换法： 1、5个1分 2、

小鱼儿/ 2022年08月20日 12:22/ 0 赞/ 183 阅读

相关 51nod 1085 01背包模板

在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。

我就是我/ 2022年08月19日 15:19/ 0 赞/ 209 阅读

相关 51nod 1086 多重背包模板

有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P

叁歲伎倆/ 2022年08月19日 15:19/ 0 赞/ 148 阅读

相关问题 : 正整数分组

题目描述将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。输入

Myth丶恋晨/ 2022年06月10日 07:14/ 0 赞/ 217 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 397 阅读

相关 51nod1085背包问题

[51Nod - 1085][] [1085 背包问题][1085] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [难度：

不念不忘少年蓝@/ 2022年05月22日 08:55/ 0 赞/ 146 阅读

相关 51nod 1396 还是01串

给定一个0-1串s，长度为n，下标从0开始，求一个位置k，满足0<=k<=n, 并且子串s\[0..k - 1\]中的0的个数与子串s\[k..n - 1\]中1的个数相等。

布满荆棘的人生/ 2021年12月10日 03:19/ 0 赞/ 207 阅读