首页 > 试题广场 >

平分物品

[编程题]平分物品
  • 热度指数:5558 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
现在有n个物品,每一个物品都有一个价值,现在想将这些物品分给两个人,要求这两个人每一个人分到的物品的价值总和相同(个数可以不同,总价值相同即可),剩下的物品就需要扔掉,现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。

要求:时间复杂度,空间复杂

输入描述:
第一行输入一个整数 T,代表有 T 组测试数据。

对于每一组测试数据,一行输入一个整数 n ,代表物品的个数。

接下来 n 个数,a[i] 代表每一个物品的价值。

1<= T <= 10
1 <= n <= 15
1 <= a[i] <= 100000



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

输入

1
5
30 60 5 15 30

输出

20

说明

样例解释,扔掉第三个和第四个物品,然后将第一个物品和第五个物品给第一个人,第二个物品给第二个人,每一个人分到的价值为,扔掉的价值为

这道题我认为是选择问题 通过dfs每一种可能的选择,找到所有可能的解法

题意转换

将题意转换很重要,题目是求最少丢掉多少物品能够平分给两个人,转换为两个人从0开始拿,计算出所有满足平分条件的最值(最少丢弃)

具体步骤

  1. 首先将题目转换为两个人从0开始拿物品,对于每一件物品开始进行选择,对于每个物品有三种选择,给第一个人、给第二个人、丢掉。

2.参数说明:nums记录n个物品的价值 ;result1、result2记录两个人目前分别拿了多少;sum记录所有元素总和,index记录选择进行到哪个元素了,n记录总共有多少个需要选择的物品

3.选择结束条件:搜索到最后一个物品 判断两者是否相等 相等则记录此时的最值
#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;
 
    }
}


发表于 2021-07-14 14:09:08 回复(3)
dfs找出物品能组成的不大于物品总价值一半的所有价值,再判断此时剩余的其他物品能不能组出这个价值,如果能组出就用这个价值去更新最大价值,物品总价值和减去最大价值的两倍就是答案。
#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;
}
发表于 2021-03-04 10:21:56 回复(6)
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)
   
A:第一个人的背包,B:第二个人的背包,C:丢弃背包
循环将每一种可能性加入ABC
当最终添加所有背包后,找出A == B背包的情况,并将其得到的C取最小值
发表于 2021-08-21 14:34:24 回复(1)
同样的思路python超时,还是得用Java或者C++
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);
    }
}


编辑于 2021-01-17 10:20:26 回复(0)
#include <bits/stdc++.h>
using namespace std;

int n,ans,sum,a[20];
void dfs(int op,int x,int y){
    if(op>=n){
        if(x==y)
        ans=min(ans,sum-x-y);
        return;
    }
    dfs(op+1,x+a[op],y);
    dfs(op+1,x,y+a[op]);
    dfs(op+1,x,y);
}
int main(){
    int T,i,j;
    cin>>T;
    while(T--){
        cin>>n;
        sum=0;
        for(i=0;i<n;i++){
            cin>>a[i];
            sum+=a[i];
        }
        ans=sum;
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}
发表于 2021-03-31 14:09:43 回复(0)
#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;
    }
}
非常简单的回溯题,无需剪枝可轻松通过所有用例,剪枝的话判断一下val_a和val_b不要大于总和一半就好。
巧用全局变量可以降低代码复杂度,不过每组数据完毕记得初始化。
发表于 2022-08-04 22:56:00 回复(0)
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)

发表于 2021-04-30 09:40:01 回复(0)
假设从一堆数字S0中取两堆数字S1,S2(S0包含S1+S2),使得S1和S2的和val1和val2相等。只要找到最大的两个相同的子和(val1、val2)即可算出需要丢弃的最小和。分别假设第i个数字被放在左边、右边、哪边都不放写出递归表达式。
#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;
    }
}

发表于 2021-04-18 02:14:23 回复(0)

二进制枚举拿走物品的方式,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;
    }
}
编辑于 2021-08-17 17:59:49 回复(0)

深度优先搜索,应该还好理解的吧,直接上源码!

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;
    }
}
发表于 2021-05-07 11:22:59 回复(2)
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)



编辑于 2023-10-17 21:21:46 回复(0)
第一反应是回溯+子集背包结果12/20 超时了,改成dfs排列组合就能过
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]);
        }
    }
}
发表于 2022-08-24 14:59:02 回复(0)
在lc上屡试不爽的方法在这里超时了。。
#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;
}


发表于 2022-07-15 19:10:51 回复(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);
    }
}


编辑于 2022-04-22 15:43:42 回复(0)

DFS解法

#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;
}


发表于 2022-03-03 10:50:52 回复(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;
}


发表于 2022-01-21 17:24:57 回复(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;
    }
}

发表于 2021-10-23 18:22:25 回复(0)
主要思路是通过multimap<int,vector<Int>>记录每一个可能的值和这个组成这个可能的值的所有组合。然后通过include来从从最末的值开始判断总和为total的组合 是否包含 总和为total/2的组合。
#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左右的时间平均复杂度。但是与此相对应的是极高的空间复杂度。

发表于 2021-10-03 00:02:47 回复(0)
#include <iostream>
#include <vector>
#include "bits/stdc++.h"
 
usingnamespacestd;
 
voiddfs(vector<int>& nums,intheapA,intheapB,intsum,intindex,intn,int&res)
{
    if(index == n)
    {
        if(heapA == heapB)
        {
            res = min(res, sum - heapA - heapB);
        }
        return;
    }
    //选择环节  每次进入选择环节都有三种选择
    dfs(nums,heapA + nums[index], heapB, sum, index + 1,n,res);
    dfs(nums,heapA,heapB + nums[index], sum, index + 1,n,res);
    dfs(nums,heapA,heapB,sum,index+1,n,res);
}
 
 
intmain() {
    intn;
    cin >> n;
    vector<vector<int>> nums;
    for(inti = 0; i < n; ++i) {
        intrownum;
        cin >> rownum;
        vector<int> rows;
        for(intj = 0; j < rownum; ++j) {
            inttemp;
            cin >> temp;
            rows.push_back(temp);
        }
        nums.push_back(rows);
    }
 
     for(intk = 0; k < nums.size(); ++k) {
        intsum = 0;
        intlen = nums[k].size();
        for(intm = 0; m < len; ++m) {
            sum += nums[k][m];
        }
        intres = INT_MAX;
        dfs(nums[k],0,0,sum,0,len,res);
        cout<<res<<endl;
    }
}
发表于 2021-08-05 18:11:58 回复(0)
#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
发表于 2021-04-10 22:04:44 回复(1)