algorithm - 在多张发票上分配一笔款项

Question

我有一个任务，可以用VB.net语言或其他编程语言来完成。我只是想知道如何做到这一点

任务描述:

我收到银行转帐，假设是 10 000。现在我必须找到可以被这个金额覆盖的发票组合 - 并且总金额 (10 000) 将被完全分配。

No Invoice| Value

Invoice 1 | 3000 
Invoice 2 | 1400
Invoice 3 | 9100
Invoice 4 | 1000
Invoice 5 | 8500
Invoice 6 | 900

例如，基于这种情况，我想支付发票 3 (9100) + 发票 6 (900) = 10 000

我试图将这个问题调整为背包算法或分区排序，但在我看来它太复杂了

Answer 1

老实说，这很像 Knapsack。不同之处在于，这里元素的重量等于它的值(value)。所以只是背包的一个特例。我继续 geeksforgeeks 并稍微修改了他们的算法，这是在 c# 中:

using System ; 

class GFG { 

    // A utility function that returns 
    // maximum of two integers 
    static int max(int a, int b) 
    { 
        return (a > b) ? a : b; 
    } 

    // Prints the items which are put 
    // in a knapsack of capacity W 
    static void printknapSack(int W, int []wt, 
                            int []val, int n) 
    { 
        int i, w; 
        int [,]K = new int[n + 1,W + 1]; 

        // Build table K[][] in bottom up manner 
        for (i = 0; i <= n; i++) { 
            for (w = 0; w <= W; w++) { 
                if (i == 0 || w == 0) 
                    K[i,w] = 0; 
                else if (wt[i - 1] <= w) 
                    K[i,w] = Math.Max(val[i - 1] + 
                            K[i - 1,w - wt[i - 1]], K[i - 1,w]); 
                else
                    K[i,w] = K[i - 1,w]; 
            } 
        } 

        // stores the result of Knapsack 
        int res = K[n,W]; 
        Console.WriteLine(res); 

        w = W; 
        for (i = n; i > 0 && res > 0; i--) { 

            // either the result comes from the top 
            // (K[i-1][w]) or from (val[i-1] + K[i-1] 
            // [w-wt[i-1]]) as in Knapsack table. If 
            // it comes from the latter one/ it means 
            // the item is included. 
            if (res == K[i - 1,w]) 
                continue; 
            else { 

                // This item is included. 
                Console.Write(wt[i - 1] + " "); 

                // Since this weight is included its 
                // value is deducted 
                res = res - val[i - 1]; 
                w = w - wt[i - 1]; 
            } 
        } 
    } 

    // Driver code 
    public static void Main() 
    { 
        int []val = { 3000, 1400, 9100, 1000, 8500, 900 }; 
        int []wt = { 3000, 1400, 9100, 1000, 8500, 900 }; 
        int W = 10000; 
        int n = val.Length; 

        printknapSack(W, wt, val, n); 
    } 
}

运行这段代码将给出输出:

10000

900 9100

一般问题的更多细节和解释https://www.geeksforgeeks.org/printing-items-01-knapsack/