2

以下のような配列があるとします

array[] = {14,10,20,4}

この配列はサブセット {14,10} と {20,4} に分割できます。これら 2 つの合計は等しいからです。

別の例は次のとおりです。

array[] = {5, 5, 15, 5}

この配列はサブセット {5,5,5} と {15} に分割できます。これら 2 つの合計は等しいからです。

しかし

array[] = {1, 5, 30}

決して等しくないため、等しいセットに分割することはできません。

どうすればそうできますか？

私のショット

var result = string.Empty;
int highestNumber = input1[0];
int sum = 0;
string set = string.Empty;

foreach (int value in input1) 
    if (value > highestNumber) highestNumber = value;

for (int i = 0; i < input1.Length; i++)
{
    var elements = input1[i];
    if (elements > 0)
    {
        if (elements != highestNumber)
        {
            sum += elements;
            set += "," + elements; 
        }
    }
}

if (sum == highestNumber)
    result = "Yes it can be partitioned" 
else
    result = "No it cannot be";

Console.WriteLine(result);

最初のものには機能しません。

このプログラムをどうするか？

4

4 に答える 4

4

指定された int 配列を、パーティションの合計が等しい 2 つのパーティションに分割します。

アプローチは次のとおりです。

  1. すべてのアイテムの合計が 2 で割り切れるかどうかを確認します (そうでない場合は分割できません)。
  2. 配列のすべてのサブセットを取得する
  3. 合計が [すべてのアイテムの合計] / 2 であるサブセットを見つけます

コードは次のとおりです。

class Program
{
    static void Main(string[] args)
    {
        var arrays = new int[][] {
            new[]{ 1, 12, 10, 2, 23 },
            new[] {14,10,20,4},
            new[] {5, 5, 15, 5},
            new[] {1, 5, 30}
        };

        foreach (var array in arrays)
        {
            Console.WriteLine(String.Format("Results for {0}:", string.Join(",", array)));
            IEnumerable<IEnumerable<int>> partitions = Partition(array);
            if (!partitions.Any()) 
                Console.WriteLine("Cannot be partitioned.");
            else
                foreach (var item in partitions)
                {
                    Console.WriteLine(string.Join(",", item));
                }
            Console.WriteLine();
        }

        Console.ReadKey();
    }

    static IEnumerable<IEnumerable<int>> Partition(int[] array)
    {
        var sum = array.Sum();
        if ((sum % 2) == 1) return Enumerable.Empty<IEnumerable<int>>();

        return Subsequences(array).Where(ss => ss.Sum(item => item) == (sum / 2));
    }

    // http://stackoverflow.com/a/3750709/201088
    private static IEnumerable<IEnumerable<T>> Subsequences<T>(IEnumerable<T> source)
    {
        if (source.Any())
        {
            foreach (var comb in Subsequences(source.Skip(1)))
            {
                yield return comb;
                yield return source.Take(1).Concat(comb);
            }
        }
        else
        {
            yield return Enumerable.Empty<T>();
        }
    }
}

出力：

Results for 1,12,10,2,23:
12,10,2
1,23

Results for 14,10,20,4:
14,10
20,4

Results for 5,5,15,5:
15
5,5,5

Results for 1,5,30:
Cannot be partitioned.
于 2013-05-09T10:04:59.760 に答える
0

配列の合計を計算し、それを 2 で割ります。これで、セットの望ましいノルム (合計値) がわかります。

パフォーマンス要件と予想されるサイズに応じて、単純なバックトラッキング アルゴリズムを使用して、すべての可能性を調べることができます。セットが持つ必要がある正確な合計がわかっているため、検索を大幅に制限できます。

于 2013-05-09T09:56:47.857 に答える
-1

最初に、リスト内の項目の組み合わせを取得するメソッドから始めることができます。これは、数値の組み合わせを作成し、それを数値からコレクションのインデックスに変換することで最も簡単に解決できます。

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IList<T> source, int n)
{
    return Combinations(source.Count, n)
        .Select(combination => combination.Select(i => source[i]));
}

public static IEnumerable<IEnumerable<int>> Combinations(int n, int p)
{
    //this is logically treated as a stack except that when enumerated it's enumerated as the 
    //reverse of a stack, which is desirable.  There is no efficient way to get the reverse iterator
    //of System.Collections.Stack so easily.  All mutations are to the end of the list.
    var stack = Enumerable.Range(0, p).ToList();

    while (stack[stack.Count - 1] < n)
    {
        //the ToList can be removed if previous sub-sequences won't be iterated 
        //after the outer sequence moves to the next item.
        yield return stack.ToList();
        int lastValue = stack.Pop();

        while (stack.Any() && lastValue + 1 > n - (p - stack.Count))
        {
            lastValue = stack.Pop();
        }

        while (stack.Count < p)
        {
            lastValue += 1;
            stack.Add(lastValue);
        }
    }
}

//simple helper method to get & remove last item from a list
public static T Pop<T>(this List<T> list)
{
    T output = list[list.Count - 1];
    list.RemoveAt(list.Count - 1);
    return output;
}

これを使用すると、特定のサイズの組み合わせだけでなく、セットのすべての組み合わせを取得するメソッドを作成するのは簡単です。

public static IEnumerable<IEnumerable<T>> AllCombinations<T>(this IList<T> source)
{
    IEnumerable<IEnumerable<T>> output = Enumerable.Empty<IEnumerable<T>>();
    for (int i = 1; i < source.Count; i++)
    {
        output = output.Concat(Combinations(source, i));
    }
    return output;
}

リストのすべての組み合わせを取得できるようになったので、LINQ を使用してジョブを完了できます。

List<int> list = new List<int>() { 5, 5, 15, 5 };

var groups = list.AllCombinations()
    .GroupBy(combination => combination.Sum());

これを使用すると、合計が同じ値になる組み合わせのすべてのグループが得られます。

于 2013-05-09T14:11:54.007 に答える