01‐Knap Pack - rFronteddu/general_wiki GitHub Wiki

You are given a total capacity and several items with a value and a weight. You are asked to to pick items such that the sum of the values is maximum but the sum of weight is smaller or equal to the total capacity.

• It is called 0/1 because you either pick an item or not
• If we could split an item, we could use a greedy solution where we sort the items and pick the best item based on value-to-weight ratio each time until we split the last one.

Rationale: Whenever a new items comes up, we must decide whether to pick it or not.

• If we pick the item, the max value will be the item value + whatever item we can fit by subtracting the new item weight from the total capacity or the best without including this item.

// wt int

//          j
// V/W    0 1 2 3 4 5 6 7
//        0 0 0 0 0 0 0 0
// 1/1 i  0 1 1 1 1 1 1 1
// 4/3    0 1 1 4 5 5 5 5
// 5/4    0 1 1 4 5 6 6 9
// 7/5    0 1 1 4 5 7 7 9

knapSack01(V, W, wt) {
    // Initialize the DP table: d[0..V.len, 0..wt]
    d[0..V.len, 0..wt] = 0

    // Loop through each item
    for i = 1 to V.len
        for j = 0 to wt
            // no pick
            d[i, j] = d[i-1, j]
            if W[i-1] <= j
                // max between pick and no pick
                d[i, j] = Max(V[i-1] + d[i-1, j-W[i-1]], d[i-1, j])

    // Return the maximum value for the full capacity
    return d[V.len, wt]
}

printKP(d, V, W, wt)
    i = V.len
    j = wt
    print("Max val: " + d[i, j])
    l = []
    while (i > 0 && j > 0) {
        if d[i,j] != d[i-1,j]
            l.push(V[i])
            j = j - W[i]
        i--   
    }
    for el : l
        print("el: " + el)