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

简介: 现在有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

相关文章
|
6月前
|
Oracle Java 关系型数据库
一次惨痛的面试:“网易提前批,我被虚拟线程问倒了”
【5月更文挑战第13天】一次惨痛的面试:“网易提前批,我被虚拟线程问倒了”
100 4
【动态规划上分复盘】下降路径最小和|礼物的最大价值
【动态规划上分复盘】下降路径最小和|礼物的最大价值
|
3月前
淘宝粗排问题之对粗排阶段打分集合归因到对应的场景内和场景外成交如何解决
淘宝粗排问题之对粗排阶段打分集合归因到对应的场景内和场景外成交如何解决
|
3月前
|
Oracle Java 关系型数据库
淘宝粗排问题之引入场景外成交样本以优化全域成交hitrate,如何解决
淘宝粗排问题之引入场景外成交样本以优化全域成交hitrate,如何解决
|
存储 算法 Go
抖音电商,提前批offer!
以前就聊过不建议普通人随便去提前批随便面试这个话题:再次认真聊一聊,为什么我建议你不要随大流去参加提前批?,但北邮本硕的学历背景 + 2段大厂实习在手,肯定不是普通人了,这个含金量还是很够的,加上后台有人私信留言问有没有提前批上岸的经验,今天就来分享一下一位师弟的提前批上岸面经。
102 1
|
12月前
|
机器学习/深度学习 算法 搜索推荐
2023秋招算法提前批:快手广告算法面经
2023秋招算法提前批:快手广告算法面经
93 0
|
机器学习/深度学习 传感器 安全
2023 年高教社杯C题蔬菜类商品的自动定价与补货决策思路及代码(持续更新)
2023 年高教社杯C题蔬菜类商品的自动定价与补货决策思路及代码(持续更新)
|
机器学习/深度学习 存储 分布式计算
KDD 2022 | 快手提出基于因果消偏的观看时长预估模型D2Q,解决短视频推荐视频时长bias难题
KDD 2022 | 快手提出基于因果消偏的观看时长预估模型D2Q,解决短视频推荐视频时长bias难题
587 0