编程题：幸运的袋子

绝地灬酷狼 2022-05-21 23:52 115阅读 0赞

## 题目描述 ##

一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。  
例如：如果袋子里面的球的号码是\{1, 1, 2, 3\}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 \* 1 \* 2 \* 3  
你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。

## 输入描述: ##

第一行输入一个正整数n(n ≤ 1000)
    第二行为n个数正整数xi(xi ≤ 1000)

## 输出描述: ##

输出可以产生的幸运的袋子数

示例1

## 输入 ##

复制

3
    1 1 1

## 输出 ##

复制

## 思路： ##

# 1.分析 #

题目可以转化成求符合条件的集合真子集个数。每次从全集中选择若干元素（小球）组成子集（袋子）。集合子集个数为2^n个，使用dfs必然超时。且此题有重复元素，那么就搜索剪枝。

## 2.搜索剪枝 ##

搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的 时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。   
所以，对程序进行优化，就成为搜索算法编程中最关键的一环。本文所要讨论的便是搜索算法中优化程序的一种基本方法叫“剪枝”。

### 3.what is it? ###

搜索的进程可以看作是从树根出发，遍历一棵倒置的树——搜索树的过程。而所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。

### 4.剪枝的原则 ###

原则之一：正确性。 因为它能够“剪去”搜索树中的一些“枝条”。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就都失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。我们利用“必要条件”来进行剪枝判断。也就是说，通过解所必须具备的特征、必须满足的条件等方面来考察待判断的枝条能否被剪枝。这样，就可以保证所剪掉的枝条一定不是正解所在的枝条。   
原则之二：准确性。   
即能够尽可能多的剪去不能通向正解的枝条。准确性可以说是剪枝优化的生命。   
原则之三：高效性。   
经常还需要提高判断操作本身的时间效率。   
综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。   
我们可以把常用的剪枝判断大致分成以下两类：   
可行性剪枝。   
最优性剪枝（上下界剪枝）。

### 代码： ###

#  #

import java.util.*;
    
    
    /**
     * Created by ASUS on 2018/6/11
     *
     * @Authod Grey Wolf
     */
    public class Test1 {
    
        public static void main(String[] args) {
            Test1 test1 = new Test1();
            test1.sys();
        }
    
        private void sys() {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int p[] = new int[n];
            int i;
            for (i = 0; i < n; i++) {
                p[i] = scanner.nextInt();
            }
            //数组进行排序
            Arrays.sort(p);
            System.out.println(getCount(p, 0, 0, 1));
        }
    
        private int getCount(int[] p, int index, int sum, int multi) {
            int count=0;
            int i;
            int len=p.length;
            for (i=index;i<len;i++){
                sum+=p[i];
                multi*=p[i];
                if(sum>multi){
                    count+=1+getCount(p,i+1,sum,multi);
                }else  if (p[i]==1){
                    count+=getCount(p,i+1,sum,multi);
                }else {
                    break;
                }
                sum-=p[i];
                multi/=p[i];
                for (;i<len-1&&p[i]==p[i+1];i++);
            }
            return count;
        }
    }

### 效果： ###

3  
1 1 1  
2

我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。