【网易算法提前批】平分物品
2022/1/4 12:07:10
本文主要是介绍【网易算法提前批】平分物品,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 一、题目描述
- 二、解题思路
- 三、C++代码
- Reference
一、题目描述
现在有n个物品,每一个物品都有一个价值,现在想将这些物品分给两个人,要求这两个人每一个人分到的物品的价值总和相同(个数可以不同,总价值相同即可),剩下的物品就需要扔掉,现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。
要求:时间复杂度 O ( 3 n ) O(3^n) O(3n),空间复杂度 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 栗子说明:样例解释,扔掉第三个和第四个物品,然后将第一个物品和第五个物品给第一个人,第二个物品给第二个人,每一个人分到的价值为60,扔掉的价值为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; }
Reference
https://www.nowcoder.com/question/next?pid=27972361&qid=1262805&tid=51115874
这篇关于【网易算法提前批】平分物品的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?