algorithm - 使用动态规划的所有可能组合

Question

我有一道看似简单的数学题。这是一个数组。

Array = { 1, 2, 3 }

需要上述数组元素的所有可能组合，使总和 = 5。

Solution: { 1, 1, 1, 1, 1 } { 1, 1, 1, 2 } { 1, 2, 2 } { 2, 3 } { 1, 1, 3 }

注意:您可以多次使用任何数组元素，前提是总和应为 5。

        int weight = 5;
        List<int> weights = new List<int>() { 1, 2 ,3};


   void function1(int weight,List<int> weights, List<List<int>> combinationlist)
    { 
    for (int i = 0; i < weights.Count; i++)
        {
            if (weight % weights[i] == 0)
            {
                int num = weight / weights[i];
                List<int> mylist = new List<int>();
                for (int j = 0; j < num; j++)
                {
                    mylist.Add(weights[i]);

                }

                if (!combinationlist.Contains(mylist))
                    combinationlist.Add(mylist);
            }


        }


    }

现在上面的函数生成了 {1,1,1,1,1} 解的简单组合。

    void function2(int weight, List<int> weights, List<List<int>> combinationlist)
    {
        int i = weights.Count - 1;
        Stack<int> mystack = new Stack<int>();
        List<int> combinationarray = new List<int>();


        foreach (var x in weights)
            mystack.Push(x);

        for (;i >= 0; i--)
        {
            if (weight <= weights[i])
                mystack.Pop();  
        }


        int remainder = 0;


        if (weight % mystack.Peek() != 0)
            remainder = weight % mystack.Peek();

            int quotient = weight / mystack.Peek();

            combine(combinationlist,combinationarray,mystack,quotient,remainder);


    }

合并函数

void combine(List<List<int>>combinations,List<int>combination,Stack<int> mystack,int quotient, int remweight)
    {

        for (int i = 0; i < quotient; i++)
        {

            combination.Add(mystack.Peek());
        }

        if (remweight > 1)
            remweight = remweight - mystack.Peek() * quotient;
        else if (remweight == 0)
        {
            if (!combinations.Contains(combination))
                combinations.Add(combination);

            return;

        }

        else
            return;

        while (mystack.Peek() > remweight )
        {
            if (mystack.Count != 0)
                mystack.Pop();
        }

        quotient = remweight / mystack.Peek();


combine(combinations, combination, mystack, quotient, remweight);


        }

所有这些工作。我只能得到两个解决方案 {2,1,1,1} {1,1,1,1,1}。

Answer 1

我将在 python 中提供答案，因为它很好地说明了算法。 Python 几乎就像是此类问题的伪代码。

# curr: a temporary list that is used only for printing the result
# arr: the list of input values
# val: the number we want to sum to
# currval: the number used so far (that will be the maximum number used so far)
def recursive_combos(curr, arr, val, currval):
    for item in arr:
        if item < currval:
            continue
        if val - item < 0:
            return
        if val - item == 0:
            print curr + [item]
            continue
        recursive_combos(curr + [item], arr, val - item, item)
    return

def combos(arr, val):
    recursive_combos([], sorted(arr), 5, min(arr) - 1)

combos([3, 1, 2], 5)

回答:

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[2, 3]

这是递归的基本说明，我认为代码大部分是不言自明的。

此解决方案中需要注意的关键事项是:

1. 需要对数组进行排序以帮助消除重复项
2. 第 4 个参数需要存在以消除重复项。我想你会发现消除它并尝试代码是一个有用的练习。可能有一种更简洁的方法来执行此操作而不是传递第 4 个参数，您可以尝试一下。
3. 这不使用动态规划的另一个关键组件内存。这将需要将结果存储在某处以获得值并查找答案。不过它可以很容易地插入。