【网易算法提前批】平分物品

简介: 现在有n个物品,每一个物品都有一个价值,现在想将这些物品分给两个人,要求这两个人每一个人分到的物品的价值总和相同(个数可以不同,总价值相同即可),剩下的物品就需要扔掉,现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。

一、题目描述

现在有n个物品,每一个物品都有一个价值,现在想将这些物品分给两个人,要求这两个人每一个人分到的物品的价值总和相同(个数可以不同,总价值相同即可),剩下的物品就需要扔掉,现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。


要求:时间复杂度O ( 3 n ) O(3^n)O(3

n

),空间复杂度O ( n ) O(n)O(n)


输入描述

第一行输入一个整数 T,代表有 T 组测试数据。
对于每一组测试数据,一行输入一个整数 n ,代表物品的个数。
接下来 n 个数,a[i] 代表每一个物品的价值。
1<= T <= 10
1 <= n <= 15
1 <= a[i] <= 100000

输出描述:

对于每一组测试数据,输出一个答案代表最少需要扔的价值。

测试用例:

输入:
1
5
30 60 5 15 30
输出:20
栗子说明:样例解释,扔掉第三个和第四个物品,然后将第一个物品和第五个物品给第一个人,第二个物品给第二个人,每一个人分到的价

二、解题思路

dfs遍历,每个节点的子结点中,有三种情况:给第一个人,给第二个人,丢掉。


几个变量说明:

n:需要选择的物品的总共数量。

sum:所有元素的总和。

全局变量res:找出满足情况的最值res,min(res, sum - result1 - result2)。


dfs的递归边界是遍历到最后一个元素,并且结束条件:搜索到最后一个物品时,判断res1和res2两者是否相等,如果相等则记录并更新res值。


三、C++代码

#include <iostream>
#include<vector>
#include<algorithm>
#include<limits.h>
using namespace std;
// 最小扔掉的价值
int res = INT_MAX;
void dfs(vector<int>& nums, int res1, int res2, int sum, int index, int n){
  //一直选到最后一个数字才返回
  if(index == n){
    if(res1 == res2){
      res = min(res, sum - res1 - res2);
      //res = sum - res1 - res2;
    }
    return;
  }
  // 每次的选择环节都有3种选择
  dfs(nums, res1 + nums[index], res2, sum, index + 1, n);
  dfs(nums, res1, res2+ nums[index], sum, index + 1, n);
  dfs(nums, res1, res2, sum, index + 1, n);
}
int main (){
  int t;
  cin >> t; // 组数
  while(t--){
    int n;//该组的物品总数
    cin >> n;
    int temp; //当前存入值
    vector<int> nums;
    for(int i =0; i < n ; i++){
      cin >> temp;
      nums.push_back(temp);
    }
    // 计算该组的元素总和
    int sum = 0;
    for(auto i : nums){
      sum += i;
    }
    //vector,res1和res2和index初始都是0,sum需单独设变量存起来
    dfs(nums, 0, 0, sum, 0, n);
    cout<<res<< endl;
    res = INT_MAX;
  }
  system("pause");
  return 0;
}

image.png

相关文章
|
1月前
|
存储 前端开发 JavaScript
循环购融合众店模式:提升复购率与用户粘性
本文介绍了如何将业务逻辑、用户交互和激励机制转化为实际的软件实现。首先,设计了数据库表结构,包括用户、商品和订单等信息。接着,提供了后端代码架构示例,使用Python和Flask框架实现用户购买商品的功能,包括计算能量值、贡献值、积分和消费券,并更新用户信息和创建订单。最后,提到了前端代码的实现,使用前端框架与用户进行交互。
|
3月前
淘宝粗排问题之对粗排阶段打分集合归因到对应的场景内和场景外成交如何解决
淘宝粗排问题之对粗排阶段打分集合归因到对应的场景内和场景外成交如何解决
|
3月前
|
Oracle Java 关系型数据库
淘宝粗排问题之引入场景外成交样本以优化全域成交hitrate,如何解决
淘宝粗排问题之引入场景外成交样本以优化全域成交hitrate,如何解决
|
4月前
|
机器学习/深度学习 自然语言处理 算法
告别重复率烦恼:论文润色降重助手帮你搞定降重!
告别重复率烦恼:论文润色降重助手帮你搞定降重!
45 0
|
自然语言处理
求助:需要训练一个行业模型,用来批量写文章。有酬谢
本人从事环保行业,比较专业的领域,有语料。想训练一个行业模型,然后用来批量写专业原创文章。有那个高手可以实现,来洽谈合作。
481 0
|
存储 算法 Go
抖音电商,提前批offer!
以前就聊过不建议普通人随便去提前批随便面试这个话题:再次认真聊一聊,为什么我建议你不要随大流去参加提前批?,但北邮本硕的学历背景 + 2段大厂实习在手,肯定不是普通人了,这个含金量还是很够的,加上后台有人私信留言问有没有提前批上岸的经验,今天就来分享一下一位师弟的提前批上岸面经。
103 1
|
机器学习/深度学习 算法 搜索推荐
2023秋招算法提前批:快手广告算法面经
2023秋招算法提前批:快手广告算法面经
98 0
|
机器学习/深度学习 算法 搜索推荐
基于动态背包的多场景广告序列投放算法
电商广告是广告主接触其目标用户的重要手段。普遍的广告目标是在预算约束下,在一定时间范围内最大化广告主累计收入。实际应用中,广告的转化通常需要对同一用户进行多次曝光,直到该用户最终购买为止。但是,现有的广告系统主要关注单次广告曝光的直接收益,而忽略了每次曝光对最终转化的贡献,因此通常属于次优解决方案。在本文中,我们将广告序列投放策略优化转化为一个动态背包问题。为求解此背包问题,我们提出了一个具有理论保证的双层优化框架,该框架在不影响求解精度同时,显着减少了原始优化问题的求解空间。在下层框架的优化中,我们引入强化学习并设计了一种有效的动作空间约减方法,提高了强化学习在实际广告应用中的探索效率。
1847 1
基于动态背包的多场景广告序列投放算法
|
数据采集 分布式计算 关系型数据库
离线计算-国内查询转换率|学习笔记
快速学习离线计算-国内查询转换率
180 0
|
算法 测试技术 C++
【网易算法提前批】平分物品
现在有n个物品,每一个物品都有一个价值,现在想将这些物品分给两个人,要求这两个人每一个人分到的物品的价值总和相同(个数可以不同,总价值相同即可),剩下的物品就需要扔掉,现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。
255 0