Skip to main content

Knapsack

Top Down

 int knapsack(int W, vector<int>& wt, vector<int>& val, int n, vector<vector<int>>& dp) {

    if (n == 0 || W == 0) return 0;

    if (dp[n][W] != -1) return dp[n][W];

    

    if (wt[n-1] <= W)

        return dp[n][W] = max(

            val[n-1] + knapsack(W - wt[n-1], wt, val, n-1, dp),

            knapsack(W, wt, val, n-1, dp)

        );

    else

        return dp[n][W] = knapsack(W, wt, val, n-1, dp);

}

Bottom Up

int knapsackBU(int W, vector<int>& wt, vector<int>& val, int n) {

    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));

    for (int i = 1; i <= n; i++) {

        for (int w = 0; w <= W; w++) {

            if (wt[i-1] <= w)

                dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w - wt[i-1]]);

            else

                dp[i][w] = dp[i-1][w];

        }

    }

    return dp[n][W];

}

Space Optimised

int knapsackSO(int W, vector<int>& wt, vector<int>& val, int n) {
    vector<int> dp(W+1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= wt[i]; w--) {
            dp[w] = max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }
    return dp[W];
}

// 1. Bounded Knapsack using Binary Decomposition
int boundedKnapsack(int W, vector<int>& wt, vector<int>& val, vector<int>& count) {
    vector<int> newWt, newVal;
    int n = wt.size();
    for (int i = 0; i < n; i++) {
        int c = count[i];
        int k = 1;
        while (c > 0) {
            int take = min(k, c);
            newWt.push_back(wt[i] * take);
            newVal.push_back(val[i] * take);
            c -= take;
            k *= 2;
        }
    }
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < newWt.size(); i++) {
        for (int w = W; w >= newWt[i]; w--) {
            dp[w] = max(dp[w], dp[w - newWt[i]] + newVal[i]);
        }
    }
    return dp[W];
}

// 2. Unbounded Knapsack
int unboundedKnapsack(int W, vector<int>& wt, vector<int>& val) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < wt.size(); i++) {
        for (int w = wt[i]; w <= W; w++) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

// 3. Exact Weight Knapsack
int exactWeightKnapsack(int W, vector<int>& wt, vector<int>& val) {
    vector<int> dp(W + 1, INT_MIN);
    dp[0] = 0;
    for (int i = 0; i < wt.size(); i++) {
        for (int w = W; w >= wt[i]; w--) {
            if (dp[w - wt[i]] != INT_MIN)
                dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W] < 0 ? -1 : dp[W];
}

// 4. Knapsack with Weight and Volume
int dualKnapsack(int W, int V, vector<int>& wt, vector<int>& vol, vector<int>& val) {
    int n = wt.size();
    vector<vector<int>> dp(W + 1, vector<int>(V + 1, 0));
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= wt[i]; w--) {
            for (int v = V; v >= vol[i]; v--) {
                dp[w][v] = max(dp[w][v], dp[w - wt[i]][v - vol[i]] + val[i]);
            }
        }
    }
    return dp[W][V];
}

// 5. Knapsack with Dependencies (Tree DP style)
unordered_map<int, vector<int>> tree;
int knapsackTree(int u, int W, vector<int>& wt, vector<int>& val, vector<vector<int>>& dp) {
    if (dp[u][W] != -1) return dp[u][W];
    int res = 0;
    for (int take = 0; take <= 1; take++) {
        if (take && wt[u] > W) continue;
        int total = take ? val[u] : 0;
        for (int child : tree[u]) {
            total += knapsackTree(child, take ? W - wt[u] : W, wt, val, dp);
        }
        res = max(res, total);
    }
    return dp[u][W] = res;
}

// 6. Meet in the Middle Knapsack
int meetInMiddle(vector<int>& wt, vector<int>& val, int W) {
    int n = wt.size();
    int half = n / 2;
    vector<pair<int, int>> A, B;
    for (int i = 0; i < (1 << half); i++) {
        int tw = 0, tv = 0;
        for (int j = 0; j < half; j++) {
            if (i & (1 << j)) { tw += wt[j]; tv += val[j]; }
        }
        if (tw <= W) A.push_back({tw, tv});
    }
    for (int i = 0; i < (1 << (n - half)); i++) {
        int tw = 0, tv = 0;
        for (int j = 0; j < (n - half); j++) {
            if (i & (1 << j)) { tw += wt[j + half]; tv += val[j + half]; }
        }
        if (tw <= W) B.push_back({tw, tv});
    }
    sort(B.begin(), B.end());
    for (int i = 1; i < B.size(); i++) B[i].second = max(B[i].second, B[i-1].second);
    int res = 0;
    for (auto [wa, va] : A) {
        int rem = W - wa;
        auto it = upper_bound(B.begin(), B.end(), make_pair(rem, INT_MAX)) - 1;
        if (it != B.begin() || it->first <= rem)
            res = max(res, va + it->second);
    }
    return res;
}

// 7. Count Number of Ways to Fill Knapsack
int countWaysKnapsack(int W, vector<int>& wt) {
    vector<int> dp(W + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < wt.size(); i++) {
        for (int w = W; w >= wt[i]; w--) {
            dp[w] += dp[w - wt[i]];
        }
    }
    return dp[W];
}

// 8. Knapsack with Forbidden Pairs
int knapsackForbidden(int W, vector<int>& wt, vector<int>& val, vector<pair<int, int>>& forbidden) {
    int n = wt.size(), maxVal = 0;
    vector<bool> valid(1 << n, true);
    for (auto [i, j] : forbidden)
        for (int mask = 0; mask < (1 << n); mask++)
            if ((mask & (1 << i)) && (mask & (1 << j))) valid[mask] = false;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (!valid[mask]) continue;
        int tw = 0, tv = 0;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) { tw += wt[i]; tv += val[i]; }
        if (tw <= W) maxVal = max(maxVal, tv);
    }
    return maxVal;
}


1. Bounded Knapsack (Limited Copies)

  • Each item has a limited count k[i]

  • Approach: Expand each item k[i] times or use Binary Representation Decomposition for optimization.

  • ♾️ 2. Unbounded Knapsack

  • Can use an item any number of times.

  • Change: Inner loop runs for (int w = wt[i]; w <= W; w++).

  • 🎯 3. Exact Weight Knapsack

  • Find the max value such that total weight = W exactly.

  • Change: Initialize dp[0] = 0, rest to -∞. Only update when a solution to that weight is possible.

  • 🎒 4. Multiple Constraints (e.g., Weight + Volume)

  • Each item has weight and volume, and the bag has max weight W and volume V.

  • Approach: 3D DP table dp[i][w][v].

  • 🎲 5. Knapsack with Item Dependencies

  • Some items can only be picked if their "parent" is picked (tree-like structure).

  • Approach: DP on tree / post-order traversal + state memoization.

  • 🎯 6. Meet-in-the-Middle Knapsack (n ≤ 40)

  • Brute-force both halves and combine smartly.

  • Used when n is too big for standard O(nW) DP.

  • 🧾 7. Count Number of Ways to Fill Knapsack to Capacity

  • Count how many distinct combinations of items give total weight W.

  • Change: Replace max() with + in DP transitions.

  • 🔒 8. Knapsack with Forbidden Pairs

  • Some item pairs cannot be taken together.

  • Approach: Add constraints in state transition or prune combinations.


Comments

Post a Comment

Popular Posts

An Ode to Rain

  An Ode to Rain “So what’s your favourite time of the year?” she asked, swinging a crossed foot lazily in the air, as she swirled a stirrer in a tiny cup of hot chocolate. Perhaps the time when I used to lick melted drops of vanilla from the back of my hand? blind to the fact that I was painting a modern art piece on the pavement with ice cream. What a charming memory.  Summer, I should say.  What about the little shivers my feet do, tucked away in the layers of heavy blankets, while my nose and ears complain of the biting cold to my toes.   Hot soups, lazy mornings, clouds from the mouth when I speak and hoodies with cosy pockets to slide my hands into.  Winter beats summer, surely.  To be fair, I was born in spring, the perfect gradient from the cold seasons to hot summers. Just the right temperature, reasonably humid with a drizzle of rain here and there. It had never been dramatic enough to create a lasting memory of itself though. Glancing out the caf...
1 comment
Read more

My Notes-app Up For Auction

It’s a late night with Alex Turner on full blast in my ears, never on the speakers though.  To make others around feel the full weight of unsolicited emotion of music, feels wrong. Who am I kidding, perhaps they don’t feel a thing. How rude. The flair of words seems to have abandoned me today so it’ll be bare bones. I find myself constantly backspacing the words I type with a vigour. A quickly written sentence followed by a slight pause full of fear, before my finger reaches out to the delete button on the far right. Desperately trying to put the tarp back on naked emotions uncovered bare. No more backspacing though. I’ve even gotten rid of the Grammarly extension. It shows me how a sentence rephrased, sounds more assertive but I digress. Enough fine tuning. Times like these I wish I had a typewriter. Imagine a canvas pedestal with hands, pointing to the parts where the acrylic paints fail to smudge. No one would ever pick up a paintbrush. Okay, enough rambling. This would have bee...
1 comment
Read more

1940 - Siege of Calais

(Audio enhances reading experience) 21 May 1940 “My good men, I come to you with grave news. The beaches of Calais will continue to be lonely tomorrow. There will be no boats at dawn.  Word has come from London and it seems lads, ‘home’, has just been turned to a mere word of nostalgia and not something we can hope to see, ever again.  The fat politicians sitting in parliament have sent their gravest apologies and perhaps think that we have surrendered to the Germans already. The Prime Minister has personally put in his apology through the wire too, cursing our enemy to his full capacity.  I did not bother noting down all that. Because I don’t for one moment believe in surrender, or defeat. Yes, even defeat. We men of war may lose our lives in the coming hours but with God himself as our witness I can assure you good lads.. A soldier never dies in vain nor defeat!  ‘Home’, has just been turned to a mere word of nostalgia and not something we can hope to s...
2 comments
Read more