首页 > 试题广场 >

篮球队

[编程题]篮球队
  • 热度指数:2948 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小Q是篮球训练队的教练,篮球队新加入了N名队员,第i名队员的篮球水平值为ai
小Q现在要把他们按照以下的要求分为A队和B队进行训练:
1、A队的队员水平值之和严格大于B队的队员水平值之和
2、对于A队中的任意一名队员,如果把他分配到B队,A队的水平值之和就会严格小于B队的水平值之和。
3、每个队员必须要加入一个队伍
小Q现在想知道有多少种方案可以按照以上要求完成分队。

输入描述:
输入包括两行, 输入的第一行为一个正整数n(2 <= N <= 50), 表示队员的数量。
第二行包括N个正整数 ai(1 <= ai <= 6 x 104), 表示每名队员的篮球水平值, 以空格分割。


输出描述:
输出一个正整数, 表示方案数。
示例1

输入

4
5 4 7 6

输出

2
'''Python写的
前后困扰了几个月,现在总结下:用一维数组dp方法(因为回溯剪枝实测真的很慢)
根据题意,A堆总重量严格大于B,但移动A堆任意一个苹果到B,A堆总重量严格小于B,说明,A和B的重量差一定小于A里面苹果重量的最小值的2倍

那么我们枚举A里面苹果最小值,假设枚举到w[i],比w[i]小的肯定都在B那里
比w[i]大的就开始01背包,01背包的结果出来之后,统计一下sum(A)-sum(B)小于2 * w[i]有多少种情况
如果我们按照能力值arry从大到小排序,那么枚举过程相当于一次01背包

'''
n = int(input())
array = list(map(int,input().split()))
#把能力值按大小逆序排列
array = sorted(array, reverse=True)

all_sum = sum(array)
result = 0
f = [1] + [0]*all_sum
for i in range(n):
    
    #因为每个队员只能"用"一次,因此必须从后往前进行,若是完全背包能用无限次,则从前往后
    
    for j in range(all_sum, array[i]-1, -1):
        
        #枚举到A队最小为array[i]时,更新A队总能力值能恰好达到j的情况(因一定有j>=arry[i],所以j不必从所有总能力值判断到0,到arry[i]即可)
        #其中放入array[i]后A队能力值能正好达到j的,放入前的能力值一定是j-array[i]
        
        f[j] = f[j] + f[j - array[i]]
        
        #判断j-arry[i]中放进arry[i]这种情况是否符合分队的两个要求,符合则结果加上能力值恰为j-arry[i]的所有情况
        
        if j > all_sum-j and j-array[i] < all_sum-j+array[i]:
            result += f[j-array[i]]
        
print(result)
#by 我之渺小
编辑于 2019-08-23 11:41:32 回复(8)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        long n_sum = 0;
        for (int i = 0; i < n; i++){
            arr[i]=sc.nextInt();
            n_sum += arr[i];
        }
        solution(arr,n,n_sum);
    }
    private static void solution(int[] arr,int n,long n_sum) {
        long ans = 0;
        //降序
        Arrays.sort(arr);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i: arr){
            list.add(i);
        }
        Collections.reverse(list);
        int[] newArr = new int[arr.length];
        for (int i = 0; i < list.size(); i++){
            newArr[i]=list.get(i);
        }
        long[][] dp = new long[2][(int)n_sum+1];
        dp[0][0] = 1;//0个商品,总价值数0的方案数
        for (int j = 1; j <= n_sum;j++){
            dp[0][j]=0;//0个商品,总价值数为j的方案数量为0
        }
        for (int i = 0; i < n; i++){
            for (int j = 1; j < n_sum; j++){
                dp[1][j]=dp[0][j];//未加入商品价值
                if (j-newArr[i]>=0){
                    dp[1][j]+=dp[0][j-newArr[i]];
                    if (j>n_sum-j&&j-newArr[i]<n_sum-j+newArr[i]){
                        ans += dp[0][j-newArr[i]];
                    }
                }
            }
            //更新
            for (int j = 1; j < n_sum; j++){
                dp[0][j] = dp[1][j];
            }
        }
        System.out.println(ans);
    }
}



编辑于 2019-08-19 11:53:15 回复(0)
//此版本解题思路参照大佬“我之渺小”,该版本为C++版本
#include <iostream>
#include <algorithm>
using namespace std;


void basketball(int* arr, int n)
{
    sort(arr, arr+n, greater<int>());
    long long sum = 0;
    long long result = 0;
    for(int i=0; i<n; i++)
    {
        sum += arr[i];
    }
    int dp[sum+1];
    dp[0] = 1;
    for(long long i=1;i<sum+1;i++)
    {
        dp[i]=0;
    }
    for(int i=0;i<n;i++)
    {
        for(long long j=sum; j>=arr[i];j--)
        {
            dp[j] = dp[j-arr[i]] + dp[j];
            if ((j > sum-j) && (j-arr[i] < sum-j+arr[i]))
            {
                result += dp[j-arr[i]];
            }
        }
    }
    cout<<result<<endl;
}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    basketball(a, n);
    return 0;
}

发表于 2019-09-04 11:39:47 回复(0)
/*
DFS,剪枝后也超时,考虑动态规划
从大到小排序 
dp[i][A_sum]为 对于第i个队员,A队到达总水平值A_sum的方案数,i之后的队员都加入B
当满足条件1,2,3 即 A_sum > n_sum-A_sum 并且 A_sum-a[i] < n_sum-A_sum+a[i] 时,
当前i队员放入A队的方案数应加入到总方案数中  ans += dp[i][A_sum-a[i]] 
dp[i][A_sum] = dp[i-1][A_sum] + dp[i-1][A_sum-a[i]]  (第i个队员加入或不加入A队)
by the way:
优化小技巧,1、除以公约数,结果不变,n_sum指数减小
*/
#include <bits/stdc++.h>
using namespace std;
#define N 50
int n, n_sum;
int a[N], dp[60000 * N] = {1};

int gcd(int x, int y)
{
    return y ? gcd(y, x % y) : x;
}
long long solve()
{
    int g = a[0];
    for(int i = 1; i < n; ++i) g = gcd(g, a[i]);
    for(int i = 0; i < n; ++i) {
        a[i] /= g;
        n_sum += a[i];
    }
    sort(a, a + n, greater<int>());
    long long ans = 0, i, A_sum;
    for(int i = 0; i < n; ++i) {
        for(int A_sum = n_sum; A_sum >= a[i]; --A_sum) {
            if(dp[A_sum - a[i]]>0 && A_sum > n_sum - A_sum && A_sum - a[i] < n_sum - A_sum + a[i]) {
                ans += dp[A_sum - a[i]];
            }
            dp[A_sum] += dp[A_sum - a[i]] ;
        }
    }
    return ans;
}
int main(void)
{
//    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }

    long long ans = solve();
    printf("%lld", ans);
    return 0;
}

编辑于 2019-07-20 23:48:03 回复(4)
//转化为0-1背包问题 设目前有A包,共n个商品,依次决定是否放入商品i,使商品总价值
//达到指定数目(未放入的,则默认加入B包)
//定义数组dp,其中dp[i][j]表示前i个商品中,使A包总价值为j的放置方案数量
//dp[i][j]=dp[i-1][j]+dp[i-1][j-arr[i]]; (不放入商品i,和放入商品i的情况。
//加号后一项需满足条件j-arr[i]>=0)
//本问题的特殊性
//在计算dp前,对价值数组arr进行降序(降序是为方便计算条件2中A包的商品最小价值);
//条件2表示 取A包内最小价值的商品放入B包,新A包总价值 < 新B包总价值
//数组dp中,dp[i][j]表示前i个商品中,使A包总价值为j的放置方案数量。此时,
//如商品i放入A包,则A包内的商品最小价值为arr[i](降序)。
//若满足j>n_sum==j && j-arr[i]<n-j-arr[i],表示当前放置方案满足1,2,3条件,
//(A包总价值j,i往后的商品都放入B包,B包总价值n_sum-j,且A包内商品最小价值arr[i])
//则 ans+=dp[i-1][j-arr[i]](ans记录满足条件1,2,3的方案总数)
// 如定义dp[n][n_sum+1],则通过率60%,内存超限。因此定义dp[2][n_sum+1],因为每次
//计算一行仅仅利用了上面一行的元素值。

#include<iostream>
#include<algorithm>
using namespace std;

void arrange(int*arr, int n){
   sort(arr, arr+n, greater<int>());  //降序
   long long n_sum=0, ans=0;
   for(int i=0; i<n; i++)
       n_sum += arr[i];
    int dp[2][n_sum+1]; // dp[0]表示在arr[i]之前的商品,放置方案数量,dp[1]表示加入商品arr[i]后,方案数量
    dp[0][0]=1; // 0个商品,总价值数为0的方案数量为1
    for(int j=1;j<=n_sum;dp[0][j]=0,j++); // 0个商品,总价值数为j(j>=1)的方案数量为0  
    for(int i=0; i<n; i++){
        for(int j=1;j<n_sum; j++){
           dp[1][j] = dp[0][j]; // 未加入商品价值arr[i]
           if(j-arr[i]>=0){
               dp[1][j] += dp[0][j-arr[i]]; // 加入商品价值arr[i]
               if (j>n_sum-j && j-arr[i]<n_sum-j+arr[i])
                   ans+=dp[0][j-arr[i]]; //满足条件1,2,3,则修改计数ans
           }
      }
      for(int j=1; j<n_sum; dp[0][j]=dp[1][j], j++);//更新dp[0]
    }
    cout<<ans<<endl;
}
int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0; i<n; i++)
        cin>>arr[i];
    arrange(arr, n);
    return 0;
}

编辑于 2019-08-01 21:20:56 回复(3)

根据顶部“我之渺小”大佬的代码改的java版本,需要注意的就是整数类型防止越界

import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        long total_sum = 0;
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
            total_sum += arr[i];
        }
        Arrays.sort(arr);

        long[] dp = new long[(int)total_sum + 1];
        dp[0] = 1;
        long ans = 0;
        for(int i = n - 1; i >= 0; i--){
            for(int j = (int) total_sum; j >= arr[i]; j--){   // 利用滚动数组从后向前更新就可以只用一维数组
                dp[j] += dp[(int)(j - arr[i])];
                if(j > total_sum - j && j - arr[i] < total_sum - j + arr[i]){
                    ans += dp[(int)(j - arr[i])];
                }
            }
        }
        System.out.println(ans);
    }
}
编辑于 2020-07-13 21:52:49 回复(0)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int AX = 3e6 + 666 ;
int a[AX] ;
int n , S ;
LL res ; 
LL dp[AX] ;
int main(){
    cin >> n ;
    S = 0 ; 
    res = 0 ;
    for( int i = 0 ; i < n ; i++ ){
        cin >> a[i] ; 
        S += a[i] ; 
    }
    memset( dp , 0LL , sizeof(dp) ) ; 
    sort( a , a + n ) ; 
    dp[0] = 1 ; 
    for( int i = n - 1 ; i >= 0 ; i-- ){ //Sa_min
        /*从大到小枚举Sa最小值,因为每次都要保证小于a[i]的Sa值的方案数dp[Sa]=0
        (因为a[i]是目前Sa的最小值,小于其的Sa方案数只能为0)*/
        for( int j = S ; j >= a[i] ; j-- ){ // 0-1:装满Sa方案数
            dp[j] += dp[j-a[i]] ; 
            int Sb = S - j ; 
            /*若满足Sa>Sb && Sa-a[i]<Sb+a[i],方案++*/
            if( j > Sb && j - a[i] < Sb + a[i] ) res += dp[j-a[i]] ; 
        }
    }
    cout << res << endl; 
    return 0 ; 
}

编辑于 2020-02-13 16:18:25 回复(0)
#include <bits/stdc++.h>
using namespace std;

bool cmp(long a, long b){
    return a>b;
}

int main(){
    int n;
    cin>>n;
    long a[n],s=0,cnt=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s += a[i];
    }
    sort(a,a+n,cmp);
    long dp[s+1];
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    for(int i=0;i<n;i++)
        for(int j=s;j>=a[i];j--){
            dp[j] += dp[j-a[i]];
            if((2*j>s) && (2*(j-a[i])<s))
                cnt += dp[j-a[i]];
        }
    cout<<cnt<<endl;
    return 0;
}

发表于 2019-10-23 02:10:46 回复(1)
Golang版,参考我之渺小
package main

import (
    "fmt"
    "sort"
)

func main() {
    var n int
    fmt.Scan(&n)
    a := make([]int, n)
    sum := 0
    for i:=0; i<n; i++ {
        fmt.Scan(&a[i])
        sum += a[i]
    }
    // 能力值倒序排列
    sort.Sort(sort.IntSlice(a))
    sort.Sort(sort.Reverse(sort.IntSlice(a)))
    res := 0
    // 01背包
    dp := make([]int, sum + 1)
    dp[0] = 1
    for i:=1; i<=sum; i++ {
        dp[i] = 0
    }
    for i:=0; i<n; i++ {
        for j:=sum; j>=a[i]; j-- {
            dp[j] = dp[j] + dp[j - a[i]]
            if (j > sum - j) && (j - a[i] < sum - j + a[i]) {
                res += dp[j - a[i]]
            }
        }
    }
    fmt.Println(res)
}


发表于 2021-08-17 10:51:29 回复(0)
/*讲一下思路吧,本质上还是背包问题
  有2个问题需要考虑
  一.
     怎么保证A队的水平值之和严格大于B队?
     假设所有队员的水平值总和为sum, A队的水平值之和为a
     显然只需要满足 a > (sum - a) 即可
  二.
     怎么保证在一的条件下,将A中任一队员替换到B队后,A队的水平值之和严格小于B队?
     假设水平值总和为sum, A队的水平值和为a
     等价于对A队的任一队员, 不妨设他的水平值为x
     都满足 a-x < (sum-a)+x  ==>  2a - sum < 2x
     因为sum和a都是定值, 显然当x取最小值时, 该式子对任意的x恒成立

  知道问题的关键在于最小值后,我们可以枚举在A队的队员水平值最低为x的情况下,
  满足上述条件的方案有多少,最后累加起来即可
  定义 dp[i][j] 代表前i个队员中可以组成水平值和为j的方案数目
  简单的01背包 转移方程就是dp[i][j] = dp[i-1][j] + dp[i-1][j-p[i]]
  然后我们将队员的水平值按从大到小排序 
  假设当前枚举的索引为i,即方案的最小值为p[i] (p数组存储的队员水平值, i >= 1)
  为了满足条件一 : j的最小值为(sum+1)/2+(sum&1 ? 0 : 1)  (j代表枚举的水平值和)
  为了满足条件二 : j的最大值为(sum+2*p[i])/2 + ((sum+2*p[i])&1 ? 0 : -1)
  然后从小到大将可行的方案累加起来
  
  这里有一个小问题是,j不能取得过大。
  按照题目所给的条件,j最大可以为3000000,这会直接导致memory超限
  不过实际上没有必要取这么大,经过不断的测试发现,j取851479为最佳
*/
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
static constexpr ll M = 851479;
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        int p[n];
        ll sum = 0;
        for (int i = 0; i < n; ++i)
            scanf("%d", &p[i]), sum += p[i];
        sort(p, p+n, [](int a, int b){
            return a > b;
        });
        int dp[n+1][M+1];
        for (int i = 0; i <= M; ++i)
            dp[0][i] = 0;
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j <= M; ++j)
            {
                dp[i][j] = dp[i-1][j];
                if (j >= p[i-1]) dp[i][j] += dp[i-1][j-p[i-1]];
            }
        ll res = 0;
        for (int i = 1; i <= n; ++i)
        {
            ll l = (sum+1)/2 + (sum&1 ? 0 : 1);
            ll r = (sum+2*p[i-1])/2 + ((sum+2*p[i-1])&1 ? 0 : -1);
            r = min(r, M);
            for (ll j = l; j <= r; ++j)
                if (j-p[i-1] >= 0) res += dp[i-1][j-p[i-1]];
        }
        printf("%lld\n", res);
    }
}


编辑于 2021-08-13 17:58:29 回复(0)
这哪是中级的,这是高级题目!
发表于 2021-02-25 15:31:10 回复(0)
//参照前面的各位大佬 加了更易懂的解释
//01背包问题

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int[] arr = new int[len];
        long sum = 0;
        for (int i = 0; i < len; i++){
            arr[i] = in.nextInt();
            sum += arr[i];
        }
        Arrays.sort(arr);
        long ans = 0;
        long[] dp = new long[(int)sum + 1];
        // 分配初始值
        dp[0] = 1;
        for (int i = len - 1; i >= 0; i--){
            // j代表B队的当前总价值,j - arr[i]代表A队总价值
            for (int j = (int)sum; j >= arr[i]; j--){
                // 加上i的总价值
                dp[j] += dp[j - arr[i]];
                // 如果交换后B > A(j > sum - j)   交换前A > B(sum - (j - arr[i]) > j - arr[i]),
                if (j > sum - j && sum - (j - arr[i]) > j - arr[i]){
                    ans += dp[j - arr[i]];
                }
            }
        }
        System.out.println(ans);
    }

}

发表于 2020-08-06 11:48:09 回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//队员的数量
        List<Long> levelsList = new ArrayList<>();//队员的水平值
        long sumLevel = 0;//总的水平值
        for (int i = 0; i < n; i++) {
            long level = sc.nextLong();
            levelsList.add(level);
            sumLevel += level;
        }

        levelsList.sort((a, b) -> (int) (b - a));//降序排列
        long[] levels = levelsList.stream().mapToLong(Long::valueOf).toArray();

        long[][] dp = new long[2][(int) sumLevel + 1];
        dp[0][0] = 1;//初始化 dp 数组 : 0 个队员,水平值为 0
        long plans = 0;//可选的方案数

        for (int i = 0; i < n; i++) {//队员(商品)[水平值已降序]
            for (int j = 1; j < sumLevel; j++) {//水平值(背包内物品总重量)
                dp[1][j] = dp[0][j];//尚未加入队员 i 的水平值
                if (j - levels[i] >= 0) {
                    if (j > sumLevel - j && j - levels[i] < sumLevel - j + levels[i]) {
                        plans += dp[0][(int) (j - levels[i])];
                    }
                    dp[1][j] += dp[0][(int) (j - levels[i])];//加入队员 i 的水平值
                }
            }
            for (int j = 1; j < sumLevel; j++) {
                dp[0][j] = dp[1][j];
            }
        }
        System.out.println(plans);
    }
}


发表于 2020-04-05 01:54:35 回复(0)
#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e6 + 10;

typedef long long ll;

ll dp[maxn],sum = 0;
ll a[maxn];
bool cmp(int a,int b){return a > b;}

int main()
{
    int n;scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%lld",&a[i]),sum += a[i];
    sort(a + 1,a + 1 + n,cmp);
    
    dp[0] = 1;
    ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = sum; j >= a[i]; j--)
        {
            dp[j] += dp[j - a[i]];
            if(j > sum - j && j - a[i] < sum - j + a[i])
                ans += dp[j - a[i]]; // 这个方案考虑近答案
            
        }
        
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2020-03-21 16:08:37 回复(0)
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include  <ctime>


using namespace std;

static int  allcount = 0;

void backtrack(vector<int>arr, vector<int> A, vector<int> B, int index)
{
	if (index == arr.size())
	{
		int sumA = 0;
		int sumB = 0;
		for (int i = 0; i < A.size(); ++i)
		{
			sumA += A[i];
		}
		for (int j = 0; j < B.size(); ++j)
		{
			sumB += B[j];
		}
		if (sumA > sumB)//A严格大于B
		{
			
			for (int i = 0; i < A.size(); ++i)
			{
				if (sumA - A[i] >= sumB + A[i])
					return;
			}
			allcount++;
		/*	cout << "ARR" << endl;
			for (auto s : A)
			{
				cout << s << " ";
			}
			cout << endl;
			for (auto s : B)
			{
				cout << s << " ";
			}
			cout << endl;*/
		}
		return;

	}
	A.push_back(arr[index]);
	backtrack(arr, A, B, ++index);
	A.pop_back();
	index--;
	B.push_back(arr[index]);
	backtrack(arr, A, B, ++index);
	B.pop_back();


}


int main()
{
	int n;
	vector<int> arr;
	cin >> n;
	int num;
	while (n--)
	{
		cin >> num;
		arr.push_back(num);
	}

	vector<int>A, B;
	backtrack(arr, A, B, 0);
	cout << allcount << endl;

//	system("pause");
	return 0;
}


只通过30%。
发表于 2019-08-16 11:26:28 回复(0)
#coding:utf-8
n = int(input())
arrs = list( map(int,input().split()))
arrs = sorted(arrs,reverse=True)
all_sum = sum(arrs)
res = 0
dp = [[0 for i in range(all_sum+1)] for i in range(2)]
for i in range(all_sum+1):
    dp[0][i] = 0
dp[0][0] = 1
for i in range(0,n):
    for j in range(1,all_sum+1):
        dp[1][j] = dp[0][j]
        if arrs[i] <= j:
            dp[1][j] = dp[1][j] + dp[0][j-arrs[i]]
            if j>all_sum-j and j-arrs[i]<all_sum-j+arrs[i]:
                res = res + dp[0][j-arrs[i]]
    for j in range(1,all_sum):
        dp[0][j] = dp[1][j]
print(str(res))

用python照着通过的C++打的,居然只通过50%,时间差这么大吗?
发表于 2019-08-15 00:52:58 回复(1)
请问用dfs不会超时吗?我怎么觉得怎么都得超时呢?
发表于 2019-07-28 14:57:04 回复(1)
 // ConsoleApplication10.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
static int  cnt = 0;
using namespace std;

int sum(vector<int> temp)
{
    vector<int>::iterator it;
    int sumt=0;

    for (vector<int>::iterator it = temp.begin(); it != temp.end(); it++)
    {
        sumt += *it;
    }
    return sumt;
}
static int  count = 0;
void dg(vector<int> _s, vector<int> _A, vector<int> _B,int num)
{
    
    if ((_A.size() + _B.size() == num))
    {
        sort(_A.begin(),_A.end());
        sort(_B.begin(), _B.end());
        for each (int k  in _A)
        {
            cout << k << "  ";

        }
        cout << endl;
        for each (int k  in _B)
        {
            cout << k << "  ";

        }
        cout << endl;
        if (sum(_A) > sum(_B))
        {
            if (sum(_A) - sum(_B) < 2 * _A[0])
                cnt++;
        }
        

    }
    if (!_s.empty())
    {
        int mm = _s.back();
        _A.push_back(mm);
        _s.pop_back();
        dg(_s, _A, _B, num);
        _A.pop_back();
        _B.push_back(mm);
        dg(_s, _A, _B, num);
    }

}
int main()
{
    int n;
    vector<int> s, A, B;
    cin >> n;
    static int  count = 0;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        s.push_back(temp);
    }
    dg(s, A, B, n);
    cout << cnt << endl;
    system("pause");

}


发表于 2019-05-05 21:34:16 回复(0)
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
#include<stdio.h>
#include <iomanip>
#include <cstdio>
using namespace std;
vector<int> all;

void dfs(int pos, int cnt, int n, int k, int a[], int sum, bool visited[]) {
    //已标记了k个数,输出结果
    
    if (cnt == k) 
    {
        vector<int> temp;
        int SUM = 0;
        int count;
        for (int i = 0; i < n; i++)
            if (visited[i])
            {
                //cout << a[i] << ' ';
                SUM += a[i];
                temp.push_back(a[i]);
            }
        sort(temp.begin(), temp.end());
        int min = temp[0];
        if ((SUM >sum-SUM) && (SUM-min<sum-SUM+min))
            count = 1;
        else count = 0;
        all.push_back(count);
       // cout << endl;
        return;
    }

    //处理到最后一个数,直接返回
    if (pos == n) return;

    //如果a[pos]没有被选中
    if (!visited[pos]) {
        //选中a[pos]
        visited[pos] = true;
        //处理在子串a[pos+1, n-1]中取出k-1个数的子问题
        dfs(pos + 1, cnt + 1, n, k, a, sum, visited);
        //回溯
        visited[pos] = false;
    }
    //处理在子串a[pos+1, n-1]中取出k个数的问题
    dfs(pos + 1, cnt, n, k, a, sum, visited);
}
int main() {
        int i, n;
        cin>>n;
        int *a = new int[n];
        int output = 0;
        int sum=0;
        bool *visited = new bool[n];
        for (i = 0; i < n; i++)
        {
            cin >> a[i];
            sum += a[i];
            visited[i] = false;
        }
        for (int k = 1; k < n; k++)
            dfs(0, 0, n, k, a, sum, visited);
        for (int j = 0; j < all.size(); j++)
            output+= all[j];
        cout << output;
        cout << endl;
        system("pause");
        delete[] a;
        delete[] visited;
    
        getchar();
        return 0;
}


发表于 2019-04-29 23:34:39 回复(0)