Nasıl bir verilen son numara eklemek sayılar kümesi verilen itibaren eklemeler tüm olası kombinasyonları test hakkında gitmek istiyorsunuz?

Örnek:

• Numaraları eklemek için: {1,5,22,15,0,...}
• İstenilen sonuç: 12345

P. S: matematik ve adapte olmak nasıl merak ettim forte benim kod değil gibi. bu sorun Soran

Bu sorun, tüm olası meblağlar hedefe ulaşmak o filtreleyerek özyinelemeli bir kombinasyonu ile çözülebilir. Burada Python: algoritma

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i 1:]
        subset_sum(remaining, target, partial   [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

Algoritmalar bu tür çok iyi Standford's Abstract Programming lecture - Bu videoyu şiddetle tavsiye özyineleme çözümleri permütasyon oluşturmak için nasıl çalıştığını anlamak için aşağıdaki açıklanmıştır.

Edit

Burada, aynı algoritma Java sürümü:

package tmp;

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,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

Aynı sezgisel. Benim Java biraz paslı ama anlamak kolay olduğunu düşünüyorum.

C# Java çözüm dönüştürme:(@JeremyThompson tarafından)

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

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

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s  = x;

    if (s == target)
        Console.WriteLine("sum("   string.Join(",", partial.ToArray())   ")="   target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i  )
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i   1; j < numbers.Count; j  ) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Ruby çözüm:(@emaillenin tarafından)

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, : 
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i 1)
    subset_sum(remaining, target, partial   [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Edit: karmaşıklığı tartışma

Başkalarına söz olarak bu NP problem. Üstel zaman O(2^n), n için örneğin=10 1024 olacak Olası çözümler içinde çözülebilir. Ulaşmaya çalıştığınız hedefler düşük bir dizi varsa o zaman bu algoritma çalışır. Örneğin:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) hedef asla Olası çözümler filtrelemek için alır çünkü 1024 dalları oluşturur.

Diğer yandan subset_sum([1,2,3,4,5,6,7,8,9,10],10) 10 ulaşmak için hedef çok kombinasyon filtre alır, çünkü sadece 175 dalları oluşturur.

N Target büyük doğal sayı çözümü yaklaşık bir sürümü içine taşımak gerekir.