6

私はこのような整数のセットを持っています

{1,4,5,2,7,8,-3,-5,-6,9,3,-7,-1,5,6}

入力がユーザーから取得されるため、セットには任意の数のアイテムを含めることができますこのセットから、合計がゼロに等しいすべての可能なサブセットを見つける必要があります。たとえば、この場合、上記のセットでは、サブセットは次のようになります

{(1,2,-3)}

{(1,-1)}

{(3,-3)}

{(5,-5)}

などなど

targetこのコードを試しましたが、ゼロに設定しているときに答えが返されません。

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {

    static void sum_up_recursive(ArrayList<Integer> numbers, int target,
                                 ArrayList <Integer> partial)
    {
        int s=0;
        for (int x: partial) s += x;
        if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);

        if (s >= target)
            return;

        for(int i=0;i<numbers.size();i++) {
            ArrayList<Integer> remaining = new ArrayList<Integer>();
            int n = numbers.get(i);
            for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
            ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
            partial_rec.add(n);
            sum_up_recursive(remaining,target,partial_rec);
        }
    }

    static void sum_up(ArrayList<Integer> numbers, int target) 
    {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }

    public static void main(String args[]) {
        Integer[] numbers = {3,4,6,4,5,2,6};
        int target = 9;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}
4

3 に答える 3

2

これが解決策の提案です。

最初に最初のサブ問題を解決します。すべての数値とターゲットが正の数であると仮定してから、実際の問題を解決します。

これを達成するために、私は基本的に問題をサブ問題に分解します。

例を挙げて説明しましょう：

数字：1、3、8、2、7ターゲット：10

最初に：リストを並べ替えます：番号：8,7,3,2,1ターゲット：10次に、次の問題の解決策を再帰的に見つけます。

数字：7、3、2、1ターゲット：10-8 = 2

数字：3,2,1ターゲット：10-7 = 3

数字：2,1ターゲット：10-3 = 2

数字：1ターゲット：10-1 = 9

前に大きな数を配置する目的は、この数を含むソリューションをすばやく排除することです（合計がすぐに目標を超えるため）。

このサブ問題を解決するためのコメント付きコードは次のとおりです。

import java.util.ArrayList;
import java.util.List;

public class Problem {

    /*
     * Used at the end to recompose the solutions.
     * This value is null for the root problem.
     */
    private Integer nodeValue;

    //The POSITIVE target sum
    private int target;

    //List of POSITIVE numbers, supposed to be sorted
    private List<Integer> numbers;

    private List<Problem> listSubProblems;

    /*
     * Link to the parent problem.
     * Useful at the end to generate the results.
     */
    private Problem parentProblem;

    public Problem(int target, List<Integer> numbers, Integer nodeValue, Problem parentProblem){
        this.target=target;
        this.numbers=numbers;
        this.nodeValue=nodeValue;
        this.parentProblem=parentProblem;
        this.listSubProblems =new ArrayList<Problem>();
    }

    public void solve(){
        buildSubProblems();
        for(Problem problem : listSubProblems){
            problem.solve();
        }
    }

    /**
     * Builds a List of sub problems.
     * For example, if {@link #numbers} contains 9 8 5 3, with target 10
     * this method will return the following sub problems:
     *
     * <table>
     *     <tr>
     *         <td>nodeValue</td><td>target</td><td>numbers</td>
     *     </tr>
     *     <tr>
     *         <td>9</td><td>10-9=1</td><numbers>8 5 3</numbers>
     *     </tr>
     *     <tr>
     *         <td>8</td><td>10-8=2</td><numbers>5 3</numbers>
     *     </tr>
     *     <tr>
     *         <td>5</td><td>10-5=5</td><numbers>3</numbers>
     *     </tr>
     *
     * </table>
     *
     */
    private void buildSubProblems(){

        int numbersSize=numbers.size();

        /*
         * Numbers are supposed to be positive so if the target is negative,
         * there is no chance to find a valid solution.
         * As the list of numbers is sorted, the case when target < 0 happens quickly
         * Hence, it quickly removes combinations implying big numbers
         */
        if(target>=0 && numbersSize> 1){

            for(int i=0;i<numbersSize;i++){
                Integer nodeValue=numbers.get(i);
                List<Integer> subList=numbers.subList(i+1,numbersSize);
                int newTarget=this.target-nodeValue;
                Problem problem=new Problem(newTarget, subList, nodeValue, this);
                System.out.println("Created problem: "+problem.dump());
                this.listSubProblems.add(problem);
            }
        }
    }

    /**
     * @return True is the Problem contains exactly one number and that number equals the target.
     */
    public boolean isNodeSolution(){
        return this.target==0;
    }

    public Integer getNodeValue(){
        return this.nodeValue;
    }

    public List<Problem> getListSubProblems(){
        return this.listSubProblems;
    }

    public Problem getParentProblem(){
        return this.parentProblem;
    }

    public String dump(){
        StringBuilder sb=new StringBuilder();
        sb.append("{nodeValue: "+this.nodeValue);
        sb.append("; target: "+target);
        sb.append("; numbers:");
        for(Integer integer : numbers){
            sb.append(integer+",");
        }
        sb.append("}");
        sb.append("Valid? : "+ isNodeSolution());
        return sb.toString();
    }

}

テスト方法を示すコードは次のとおりです。

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {

    public static void main(String[] args) throws Exception{
        Integer numbers[]={1,3,8,2,7};
        int target=10;

        List<Integer> listNumbers= Arrays.asList(numbers);

        Collections.sort(listNumbers);
        Collections.reverse(listNumbers);

        //Build the root problem
        Problem problem=new Problem(target,listNumbers,null,null);

        //Solve it
        problem.solve();

        //Dump the result.
        dumpResult(problem);

        System.out.println("Done!");
    }

    private static void dumpResult(Problem problem){
        for(Problem p:problem.getListSubProblems()){
            if(p.isNodeSolution()){
                System.out.print("\nSolution :");
                dumpSolution(p);
            }
            dumpResult(p);
        }
    }

    private static void dumpSolution(Problem problem){
        //If the current node is not the root problem
        if(problem.getParentProblem()!=null){
            System.out.print(problem.getNodeValue() + ", ");
            dumpSolution(problem.getParentProblem());
        }
    }
}

そして、これが出力の例です：

Created problem: {nodeValue: 8; target: 2; numbers:7,3,2,1,}Valid? : false
Created problem: {nodeValue: 7; target: 3; numbers:3,2,1,}Valid? : false
Created problem: {nodeValue: 3; target: 7; numbers:2,1,}Valid? : false
Created problem: {nodeValue: 2; target: 8; numbers:1,}Valid? : false
Created problem: {nodeValue: 1; target: 9; numbers:}Valid? : false
Created problem: {nodeValue: 7; target: -5; numbers:3,2,1,}Valid? : false
Created problem: {nodeValue: 3; target: -1; numbers:2,1,}Valid? : false
Created problem: {nodeValue: 2; target: 0; numbers:1,}Valid? : true
Created problem: {nodeValue: 1; target: 1; numbers:}Valid? : false
Created problem: {nodeValue: 3; target: 0; numbers:2,1,}Valid? : true
Created problem: {nodeValue: 2; target: 1; numbers:1,}Valid? : false
Created problem: {nodeValue: 1; target: 2; numbers:}Valid? : false
Created problem: {nodeValue: 2; target: -2; numbers:1,}Valid? : false
Created problem: {nodeValue: 1; target: -1; numbers:}Valid? : false
Created problem: {nodeValue: 2; target: 5; numbers:1,}Valid? : false
Created problem: {nodeValue: 1; target: 6; numbers:}Valid? : false

Solution :2, 8,
Solution :3, 7, Done!

さて、これは負の数を意味する最初の問題をカバーしていません。このケースを解決するには、すべての負の数を分離し、合計を使用して負の数のすべての組み合わせを計算します。

次に、負の数の合計ごとに、正の数と対応するターゲット（初期ターゲット-負の数の合計）のみを含むサブ問題を作成します。

それを改善する1つの方法：問題の複雑さは、負の数の組み合わせの数に依存します。したがって、正の数よりも負の数が多い場合は、すべての値を反転して、反転の問題を解決できます。

それを改善する別の方法：各サブ問題の正の数の合計をメモリに保持できます。sum + nodeValue <targetの場合、ブランチの探索を続けることは無意味です。

于 2013-03-21T08:10:24.120 に答える
1

私は大学時代に Google の面接でこの問題に遭遇し、非常に長い道のりで解決しました。

考えてみてください。セットが 0 になるには、負の数である必要があり、正の数のセットである必要があります。

手順:

1. Created a 2 arrays negativeNumArrays and POsitiveNumArrays
2. Create a new negative set(does not allows duplicate) which is possible sums of     negative arrays ex -
    [-1,-2,-3] = [-1,-2,-3, {-1-2=3},{-1,-3=-4},{-2,-3=-5},{-6}] = [-1,-2,-3,-4,-5,-6]
So the set looked like
Key:Value
"1" =-1
"2" = -2
...
"2:3"=-5 
"1:2:3"=-6

Here 
"N6" = -6

3. For this new set of negative array find combination in positive 
   array which matches any of the 6 negative arrays.

Same as above say positive numbers are 3 and 4
So the set would look like
"3"=3

"4"=4

"3:4"=7


Now simple compare the two sets and see which of these are equal
So for example Negative Set "1:3" = Positive Set "4"
and hence use Stringtokenizer to get the numbers from set key {-1,-3,4}
于 2013-03-20T20:12:25.157 に答える
0

partialが空かどうかをチェックしていません。その場合、 == 0sum_up_recursive()のときに最初の試行ですぐに戻ります。これを試してください。target

if (partial.size() > 0) {
    for (int x : partial)
        s += x;

    if (s == target)
        System.out.println("sum(" + Arrays.toString(partial.toArray()) + ")=" + target);

    if (s >= target)
        return;
}

使用しているアルゴリズムを大幅に改善する他の方法があるかもしれないことに注意してください。コードが期待どおりに機能しない理由に答えているだけです。

于 2013-03-20T22:24:52.133 に答える