algorithm
Rucksack Problem

Bemerkungen

Grundlagen des Rucksackproblems

Das Problem : Bestimmen Sie für eine Reihe von Elementen, bei denen jedes Element ein Gewicht und einen Wert enthält, die Anzahl der Elemente, die in eine Sammlung aufgenommen werden sollen, so dass das Gesamtgewicht kleiner oder gleich einer bestimmten Grenze ist und der Gesamtwert so groß wie möglich ist .

Pseudocode für Knapsack Problem

Gegeben:

1. Werte (Array v)
2. Gewichte (Array w)
3. Anzahl verschiedener Elemente (n)
4. Kapazität (W)

for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

Eine einfache Implementierung des obigen Pseudocodes mit Python:

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W+1)] for x in range(n+1)]
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
    return K[n][W]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))

Ausführen des Codes: Speichern Sie dies in einer Datei mit dem Namen knapSack.py

$ python knapSack.py
220

Zeitkomplexität des obigen Codes: O(nW) wobei n die Anzahl der Elemente und W die Kapazität des Rucksacks ist.

In C # implementierte Lösung

public class KnapsackProblem
{
    private static int Knapsack(int w, int[] weight, int[] value, int n)
    {
        int i;
        int[,] k = new int[n + 1, w + 1];
        for (i = 0; i <= n; i++)
        {
            int b;
            for (b = 0; b <= w; b++)
            {
                if (i==0 || b==0)
                {
                    k[i, b] = 0;
                }
                else if (weight[i - 1] <= b)
                {
                    k[i, b] = Math.Max(value[i - 1] + k[i - 1, b - weight[i - 1]], k[i - 1, b]);
                }
                else
                {
                    k[i, b] = k[i - 1, b];
                }
            }
        }
        return k[n, w];
    }

    public static int Main(int nItems, int[] weights, int[] values)
    {
        int n = values.Length;
        return Knapsack(nItems, weights, values, n);
    }
}