现在有n个物品,每一个物品都有一个价值,现在想将这些物品分给两个人,要求这两个人每一个人分到的物品的价值总和相同(个数可以不同,总价值相同即可),剩下的物品就需要扔掉,现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。
要求:时间复杂度,空间复杂度
第一行输入一个整数 T,代表有 T 组测试数据。对于每一组测试数据,一行输入一个整数 n ,代表物品的个数。
接下来 n 个数,a[i] 代表每一个物品的价值。1<= T <= 101 <= n <= 151 <= a[i] <= 100000
对于每一组测试数据,输出一个答案代表最少需要扔的价值。
1 5 30 60 5 15 30
20
样例解释,扔掉第三个和第四个物品,然后将第一个物品和第五个物品给第一个人,第二个物品给第二个人,每一个人分到的价值为,扔掉的价值为。
这道题我认为是选择问题 通过dfs每一种可能的选择,找到所有可能的解法
题意转换
将题意转换很重要,题目是求最少丢掉多少物品能够平分给两个人,转换为两个人从0开始拿,计算出所有满足平分条件的最值(最少丢弃)
具体步骤
首先将题目转换为两个人从0开始拿物品,对于每一件物品开始进行选择,对于每个物品有三种选择,给第一个人、给第二个人、丢掉。
2.参数说明:nums记录n个物品的价值 ;result1、result2记录两个人目前分别拿了多少;sum记录所有元素总和,index记录选择进行到哪个元素了,n记录总共有多少个需要选择的物品
#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<bits/stdc++.h> //定义两组数据的累加和 从0开始dfs每种可能,遇到两者相同的情况,就记录此时需要扔掉 //选择问题 两个人从0开始拿物品,遇到一个物品有三种选择,给第一个人,给第二个人,扔掉。 //走到结尾就找到舍弃价值最小的那一个节点 int res = INT_MAX;//最小扔掉的价值 void dfs(vector<int>& nums,int result1,int result2,int sum,int index,int n) { //一直选择到最后一个数字才返回 if (index == n) { if (result1 == result2) { res = min(res, sum - result1 - result2); } return; } //选择环节 每次进入选择环节都有三种选择 dfs(nums,result1 + nums[index], result2, sum, index + 1,n); dfs(nums,result1,result2 + nums[index], sum, index + 1,n); dfs(nums,result1,result2,sum,index+1,n); } int main() { int t; cin >> t; while (t--)//一个while输出一个答案 { 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; } dfs(nums, 0, 0, sum, 0, n); cout << res << endl; res = INT_MAX; } }
#include<iostream> #include<stdio.h> #include<vector> using namespace std; bool judge(vector<int>& v, vector<int>& mark, int n, int tsum) { bool ret = false; vector<int> tv(1,0); for(int i=0; i<n; i++) { if(mark[i]==0) { int len = tv.size(); for(int j=0;j<len;j++) { if(tv[j]+v[i]==tsum) { ret = true; break; } else tv.push_back(tv[j]+v[i]); } } if(ret) break; } return ret; } void search(vector<int>& v, vector<int>& mark, int i, int n, int tsum, int sum, int& ans) { if(i>n || tsum*2>sum) return; if(i==n) { if(judge(v, mark, n ,tsum)) { if(tsum>ans) ans=tsum; } return; } mark[i]=1; search(v, mark, i+1, n, tsum + v[i], sum, ans); mark[i]=0; search(v, mark, i+1, n, tsum, sum, ans); } int main() { int T; scanf("%d",&T); while(T--) { int n,sum=0,ans=0; scanf("%d",&n); vector<int> v(n); vector<int> mark(n,0); for(int i=0;i<n;i++) { scanf("%d",&v[i]); sum+=v[i]; } search(v, mark, 0, n, 0, sum, ans); printf("%d\n",sum-2*ans); } return 0; }
T = int(input()) #取出循环组数 for x in range(T): n = int(input()) #取出一组内数字个数 a = list(map(int,input().split())) #遍历数组保存至list ans = 10000000000 def DFS(x, n, A, B, C): global ans if C > ans:return #递归终止条件 if x>=n: if A == B: ans = min(ans,C) #取C的最小值 return DFS(x+1,n,A+a[x],B,C) DFS(x+1,n,A,B+a[x],C) DFS(x+1,n,A,B,C+a[x]) DFS(0, n, 0, 0, 0) print(ans)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { static int sum = 0; static int res = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; while((line = br.readLine()) != null){ int T = Integer.parseInt(line); while(T > 0) { int n = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().split(" "); int[] weights = new int[n]; sum = 0; res = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { weights[i] = Integer.parseInt(strArr[i]); sum += weights[i]; } dfs(0, 0, 0, weights); System.out.println(res); T --; } } } public static void dfs(int heap1, int heap2, int start, int[] weights){ // 如果两个人的物品价值相等,则计算一次扔掉的物品的价值 if(heap1 == heap2) res = Math.min(res, sum - heap1 - heap2); if(start == weights.length) return; // 将当前物品分别分配给两个人进行尝试 dfs(heap1 + weights[start], heap2, start + 1, weights); dfs(heap1, heap2 + weights[start], start + 1, weights); dfs(heap1, heap2, start + 1, weights); } }
#include <bits/stdc++.h> using namespace std; int res = INT_MAX; vector<int> items; void dfs(int index, int val_a, int val_b, int val_x) { if (index == items.size()) { if (val_a == val_b) res = min(res, val_x); return; } dfs(index + 1, val_a + items[index], val_b, val_x); dfs(index + 1, val_a, val_b + items[index], val_x); dfs(index + 1, val_a, val_b, val_x + items[index]); } int main() { int n; cin>>n; for (int i=0;i<n;i++) { int pts; cin>>pts; for (int j=0;j<pts;j++) { int cur; cin>>cur; items.emplace_back(cur); } dfs(0, 0, 0, 0); cout<<res<<endl; items.clear(); res = INT_MAX; } }
T = int(input()) for cas in range(T) : n = int(input()) a = list(map(int, input().split())) ans = 1000000000 def DFS(x, n, A, B, C) : global ans if C > ans : return if x >= n : if A == B : ans = min(ans, C) return DFS(x + 1, n, A + a[x], B, C) DFS(x + 1, n, A, B + a[x], C) DFS(x + 1, n, A, B, C + a[x]) DFS(0, n, 0, 0, 0) print(ans)
#include <bits/stdc++.h> using namespace std;
int maxval=0;
void find_value(int a, int b, int arr[], int i, int range){
if (a==b) maxval=max(maxval,a);
if (i==range){
return ;
}else{
find_value(a+arr[i], b, arr, i+1, range);
find_value(a, b+arr[i], arr, i+1, range);
find_value(a, b, arr, i+1, range);
}
}
int main(){
ios::sync_with_stdio(false);
int set_num=0;
cin>>set_num;
for (int i=0; i<set_num; i++){
maxval=0;
int num;
cin>>num;
int arr[num];
//vector<int> vec(num);
for (int j=0; j<num; j++){
cin>>arr[j];
}
find_value(0, 0, arr, 0, num);
int sum=0;
for (int j=0; j<num; j++){
sum=sum+arr[j];
}
cout<<sum-maxval*2<<endl;
}
}
二进制枚举拿走物品的方式,3^n次,再判断剩下的物品能否平分,取最小即可。
#include <bits/stdc++.h> using namespace std; class Solution{ public: bool check(vector& tmp,int tmpSum){ if (tmpSum%2!=0) return false; int n=tmp.size(); for (int i=(1<<n)-1;i;--i){ int ss=0; for (int j=0;j<n;++j) if ((i>>j)&1==1) ss+=tmp[j]; if (ss==tmpSum/2) return true; } return false; } int solve(vector & arr){ int n=arr.size(); int arrSum=accumulate(arr.begin(), arr.end(), 0); int ans=arrSum; for (int i=(1<<n)-1;i;--i){ vector tmp; int tmpSum=0; for (int j=0;j<n;++j){ if ((i>>j)& 1==1) { tmp.push_back(arr[j]); tmpSum+=arr[j]; } } if (check(tmp,tmpSum)) ans=min(ans,arrSum-tmpSum); } return ans; } }; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; vector arr(n,0); for (int i=0;i<n;++i)cin>>arr[i]; Solution s; cout<<s.solve(arr)<<endl; } }
深度优先搜索,应该还好理解的吧,直接上源码!
import java.util.Scanner; /** * 深度优先搜索 */ public class Main { static int t, n, res; static int[] a; public static void main(String[] args) { Scanner sc = new Scanner(System.in); t = sc.nextInt(); while(t-- != 0){ n = sc.nextInt(); a = new int[n]; res = 0; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); res += a[i]; } //dfs(0, 0, 0, 0); System.out.println(dfs(0, 0, 0, 0)); } } public static int dfs (int i, int s1, int s2, int delete) { if (i == n) { // 当第一轮分完,进行判断 if (s1 == s2 && delete < res) res = delete; return res; //结束本轮判断 } dfs(i+1, s1+a[i], s2, delete); //把a[i]分给第一个人 dfs(i+1, s1, s2+a[i], delete); //把a[i]分给第二个人 dfs(i+1, s1, s2, delete+a[i]); //丢弃 return res; } }
from math import e from re import T import sys def judge(a): s1 = a[0] s2 = sum(a) - a[0] for i in range(len(a)): if s1 < s2: s1 = s1 + a[i+1] s2 = s2 - a[i+1] else: if s1 == s2: return True else: return False n0 = int(input()) n1 = int(input()) b = input().split() for i in range(n0): a = [int(ai) for ai in b[i*n1:i*n1+n1]] a = sorted(a, reverse=True) a_sum = 0 for i in range(n1): c = judge(a) if c: print(a_sum) break else: a_sum += a[n1-i-1] a.pop() if i == n1-1: print(False)
import java.util.*; public class Main { // 丢掉不需要的平分物品 public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for (int i = 0; i < t; i++) { int n = in.nextInt(); int[] arr = new int[n]; sum = 0; for (int j = 0; j < n; j++) { arr[j] = in.nextInt(); sum += arr[j]; } min = Integer.MAX_VALUE; dfs(arr, 0, 0, 0, 0); System.out.println(min); } } // dfs排列组合-分给三个人 static int min, sum; public static void dfs(int[] arr, int idx, int a, int b, int c) { if (a == b) { min = Math.min(min, sum-a-b); } for (int i = idx; i < arr.length; i++) { dfs(arr, i+1, a+arr[i], b, c); dfs(arr, i+1, a, b+arr[i], c); dfs(arr, i+1, a, b, c+arr[i]); } } }
#include<iostream> #include<vector> #include<numeric> #include<cmath> #include<climits> using namespace std; int divided(vector<int>& objects){ int olen = objects.size(); int total = pow(3,olen); int sum = accumulate(objects.begin(), objects.end(), 0); int ans = INT_MAX; for(int i = 0; i<total; ++i){ int v1 = 0, v2 = 0; int temp = i; for(int j = 0; j<olen; ++j){ if(temp%3 == 1) v1 += objects[j]; else if(temp%3 == 2) v2 += objects[j]; temp /= 3; } if(v1 == v2){ ans = min(ans, sum-v1*2); } } return ans; } int main(){ int N = 0; cin>>N; for(int i = 0; i<N; ++i){ int n = 0; cin>>n; vector<int> obj; for(int i = 0; i<n; ++i){ int j = 0; cin>>j; obj.push_back(j); } int ans = divided(obj); cout<<ans<<endl; } return 0; }
public class Main { static int t, n, sum; static int[] a; static int res = Integer.MAX_VALUE; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int test_number = scanner.nextInt(); // ****************** 解决输入问题 ******************** while (test_number-- != 0) { res = Integer.MAX_VALUE; int number = scanner.nextInt(); String huiche = scanner.nextLine(); sum = 0; String cost = scanner.nextLine(); String[] s = cost.split(" "); int[] cost_arr = new int[s.length]; for (int i = 0; i < s.length; i++) { cost_arr[i] = Integer.parseInt(s[i]); sum += cost_arr[i]; } dfs(0,0,0,cost_arr); System.out.println(res); } } public static void dfs(int heap1 , int heap2, int start , int[] cost_arr){ if(heap1==heap2) res = Math.min(res,sum-heap1-heap2); if(start == cost_arr.length) return; dfs(heap1+cost_arr[start],heap2,start+1,cost_arr); dfs(heap1,heap2+cost_arr[start],start+1,cost_arr); dfs(heap1,heap2,start+1,cost_arr); } }
#include <iostream> #include <vector> using namespace std; int sum; // DFS计算扔掉物品的最小价值sum void travers(int one, int another, int rest, vector<int> vec, int index) { // 剪枝降低复杂度:如果当前扔掉的物品总价值大于最小值,必然不是最优解,直接跳过 if(rest > sum) return; // 当遍历到最后一个位置的时候,如果两人分到的物品总价值相同,更新扔掉的物品总价值的最小值 if(index == vec.size()) { if(one == another) sum = min(rest, sum); return; } // 做选择:需要把当前物品分给谁,或者扔掉 travers(one+vec[index], another, rest, vec, index+1); travers(one, another+vec[index], rest, vec, index+1); travers(one, another, rest+vec[index], vec, index+1); } int main() { int T; cin >> T; for(int i = 0; i < T; i++) { int n; cin >> n; vector<int> vec; sum = 2000000; for(int j = 0; j < n; j++) { int price; cin >> price; vec.push_back(price); } travers(0, 0, 0, vec, 0); cout << sum << endl; } return 0; }
#include <bits/stdc++.h> #define INF 0x3f3f3f3f //#define mod 998244353 #define mod 1000000007 #define ll long long using namespace std; const int N=1e5+5; const double eps=1e-8; int n,m,k,q; void solve(){ int ans=INF; cin>>n; vector<int>a(n+5),vis(n+5,0); for(int i=0;i<n;i++)cin>>a[i]; function<void (int)>dfs=[&](int k){ if(k==n){ int k1=0,k2=0,k3=0; for(int i=0;i<n;i++){ if(vis[i]==0)k3+=a[i]; else if(vis[i]==1)k1+=a[i]; else k2+=a[i]; } if(k1==k2)ans=min(ans,k3); //cout<<k1<<' '<<k2<<' '<<k3<<'\n'; //return ; } else{ vis[k]=0; dfs(k+1); vis[k]=1; dfs(k+1); vis[k]=2; dfs(k+1); } }; dfs(0); cout<<ans<<'\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); cout<<fixed<<setprecision(10); int t; cin>>t; while(t--){ solve(); } return 0; }
#include <bits/stdc++.h> using namespace std; class Solution{ public: bool check(vector& tmp,int tmpSum){ if (tmpSum%2!=0) return false; int n=tmp.size(); for (int i=(1<<n)-1;i;--i){ int ss=0; for (int j=0;j<n;++j) if ((i>>j)&1==1) ss+=tmp[j]; if (ss==tmpSum/2) return true; } return false; } int solve(vector & arr){ int n=arr.size(); int arrSum=accumulate(arr.begin(), arr.end(), 0); int ans=arrSum; for (int i=(1<<n)-1;i;--i){ vector tmp; int tmpSum=0; for (int j=0;j<n;++j){ if ((i>>j)& 1==1) { tmp.push_back(arr[j]); tmpSum+=arr[j]; } } if (check(tmp,tmpSum)) ans=min(ans,arrSum-tmpSum); } return ans; } }; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; vector arr(n,0); for (int i=0;i<n;++i)cin>>arr[i]; Solution s; cout<<s.solve(arr)<<endl; } }
#include<bits/stdc++.h> using namespace std; class solution{ public: //判断一个有序数组call是否包含另一个有序数组cpart bool compare_coll(const vector<int>& call,const vector<int>& cpart){ return includes(call.begin(),call.end(),cpart.begin(),cpart.end()); } //multimap插入,对于所有的旧的map值i,插入tree[i+t]=tree[i].emplace_back(t); void tree_insert(multimap<int,vector<int>>&tree,int t){ auto tree_tem(tree); for(auto rpos=tree_tem.rbegin();rpos!=tree_tem.rend();rpos++){ vector<int> t_coll(rpos->second); t_coll.emplace_back(t); tree.insert(make_pair(t+rpos->first,t_coll)); } vector<int> tcoll; tcoll.emplace_back(t); tree.insert(make_pair(t,tcoll)); } //main function int fun(vector<int> coll,int n){ int coll_total=accumulate(coll.begin(),coll.end(),0); sort(coll.begin(),coll.end(),less<int>()); multimap<int,vector<int>> tree; //creat map for(auto elem:coll){ tree_insert(tree,elem); } //从大到小查找 for(auto pos=tree.rbegin();pos!=tree.rend();pos++){ int total=pos->first; if(total%2==1){continue;} int half=total/2; auto ppos=tree.equal_range(half); auto fpos=ppos.first; auto lpos=ppos.second; for(auto tempos=fpos;tempos!=lpos;tempos++){ if(compare_coll(pos->second,tempos->second)){return coll_total-total;} else{continue;} } } return coll_total; } }; int main(){ //initialize int T; cin>>T; while(T--){ int n; cin>>n; vector<int> coll(n); for(auto&elem:coll){ cin>>elem; } //mian function solution sol; int result=0; result=sol.fun(coll,n); cout<<result<<endl; } return 0; }大概n^4~n^5左右的时间平均复杂度。但是与此相对应的是极高的空间复杂度。
#include <bits/stdc++.h> using namespace std; int ans; int v[20]; int n; void dfs(int index, int a, int b) { if(a == b) ans = max(ans, a + b); if(index == n) return; dfs(index + 1, a + v[index], b); dfs(index + 1, a, b + v[index]); dfs(index + 1, a, b); } int main() { int T; cin >> T; while(T--) { ans = 0; cin >> n; for(int i = 0; i < n; i++) cin >> v[i]; int total = accumulate(v, v + n, 0); dfs(0, 0, 0); cout << total - ans << endl; } return 0; }dfs