c# - 计算所有可能的排列/组合，然后检查结果是否等于一个值

Question

最好的解释方式是举个例子:

您正在用 2000 美元光顾一家商店，您的目标是在旅行结束时获得 0 美元。您不知道有多少商品可用，也不知道它们的价格。

假设目前有 3 件商品的价格分别为 1000 美元、750 美元和 500 美元。(重点是计算所有可能的解决方案，而不是最有效的解决方案。)

您可以花费 2000 美元，这意味着:

You can buy the $1000 item 0, 1 or 2 times.
You can buy the $750 item 0, 1 or 2 times.
You can buy the $500 item 0, 1, 2, 3 or 4 times.

最后我需要能够得到所有的解决方案，在这种情况下就是

2*$1000
1*$1000 and 2*$500
2*$750 and 1*$500
4*$500

旁注:你不能有重复的解决方案(像这样)

1*$1000 and 2*$500
2*$500 and 1*$1000

这是我尝试过的:

你首先调用这个函数使用

 goalmoney = convert.ToInt32(goalMoneyTextBox.Text);
 totalmoney = Convert.ToInt32(totalMoneyTextBox.Text);
 int[] list = new int[usingListBox.Items.Count];
 Calculate(0, currentmoney, list);

函数:

    public void Calculate(int level, int money, int[] list)
    {
        string item = usingListBox.Items[level].ToString();
        int cost = ItemDict[item];
        for (int i = 0; i <= (totalmoney / cost); i++)
        {
            int[] templist = list;
            int tempmoney = money - (cost * i);
            templist[level] = i;
            if (tempmoney == goalmoney)
            {
                resultsFound++;
            }
            if (level < usingListBox.Items.Count - 1 && tempmoney != goalmoney) Calculate(level + 1, tempmoney, templist);
        }
    }

Answer 1

您的问题可以简化为一个众所周知的数学问题，标记为 Frobenius equation这与众所周知的密切相关Coin problem .假设您有 N 件商品，其中第 i 件商品的价格为 c[i]，而您恰好需要花费 S$。所以你需要找到方程的所有非负整数解(或者判断是否根本没有解)

c[1]*n[1] + c[2]*n[2] + ... + c[N]*n[N] = S

其中所有 n[i] 都是未知变量，每个 n[i] 是第 i 类购买商品的数量。

这个方程可以用多种方法求解。以下函数 allSolutions(我想它可以进一步简化)找到给定方程的所有解:

public static List<int[]> allSolutions(int[] system, int total) {
    ArrayList<int[]> all = new ArrayList<>();
    int[] solution = new int[system.length];//initialized by zeros
    int pointer = system.length - 1, temp;
    out:
    while (true) {
        do { //the following loop can be optimized by calculation of remainder
            ++solution[pointer];
        } while ((temp = total(system, solution)) < total);

        if (temp == total && pointer != 0)
            all.add(solution.clone());
        do {
            if (pointer == 0) {
                if (temp == total) //not lose the last solution!
                    all.add(solution.clone());
                break out;
            }
            for (int i = pointer; i < system.length; ++i)
                solution[i] = 0;
            ++solution[--pointer];
        } while ((temp = total(system, solution)) > total);
        pointer = system.length - 1;
        if (temp == total)
            all.add(solution.clone());
    }
    return all;
}

public static int total(int[] system, int[] solution) {
    int total = 0;
    for (int i = 0; i < system.length; ++i)
        total += system[i] * solution[i];
    return total;
}

在上面的代码中，system 是系数数组c[i]，total 是S。有一个明显的限制:system 不应有任何零元素(这会导致无限多的解决方案)。对上述代码稍加修改就可以避免这种限制。