Knapsack

Fractional knapsack

greedy, sort items by value/wt and pick max ones

0/1 Knapsack - O(nw) time and O(nw) space variant

• def: f(w) ⇒ max value s.t. wt ⇐ w
• trans: for each item, for wt (rev) : f(w) = max{ self, f(w-wt) + val }

O(nw) time, O(w) space

printing items

use the 2d variation, dp(i,w) → first i items, wt w

rem: 2d way needs you to copy dp(i-1) over to dp(i), this is the not take case

compare f(i,W) and f(i-1,W) ⇒ note that this is not for weight exactly w but ⇐w. If same, you don’t need the ith item in your solution set ( note that this is one valid set )

0/1 KP - printing must and maybe set

This problem: https://atcoder.jp/contests/abc441/tasks/abc441_f

method 1: meet in the middle

use prefix of items and suffix of items to find “with i” and “without i” best values

make the 2d calc, once as items in initial order (pref(i,w)) and once with items in reverse order (suff(i,w))

without is easy, just skip i and connect prefix and suffix. without i = max{ for w : pref(i-1,w) + suff(i+1,W-w) }

with is similarly, with = val(i) + max{ for w: pref(i-1,w) + suff(i-1,W-w-wt(i)) }. basically you push in i and account for rest

must ⇒ with is global max ( this is just pref(n,w) ), and without < global max maybe ⇒ with is global max and without is global max never ⇒ without = global max

This is O(nw) in time and mem

method 2: inverse dnc

visualise the opertaion done as “processing an invidual item on a dp array”. I do a “push” operation and it applies transitions to the dp array. Inverse dnc is similar, if you are at leaf, you want to reach a state where all but current item is “pushed”.

key idea is: shared processing and shared state so that segments get shared.

copy full dp array at each node

• sharing: when at root and you go to left, you know all nodes in left subtree need right processed, this is done once.
• copying: both left and right work with exclusive ranges, hence you need to copy

root → 0 to n-1, left is 0 to mid, right is mid+1 to n-1.

trading time for memory improv. time is O(nw log n) and mem is O(w log n).

• note: you can do 10^8 mem in contests, that works

this is the core code

auto f = [&](auto &&f, int l, int r, vector<int> &cur_dp) -> void {
    if (l == r) {
        int without = cur_dp[w];
 
        int with = -INF;
        if (wt[l] <= w) {
            with = cur_dp[w - wt[l]] + val[l];
        }
 
        if (with == best_val) {
            if (without < best_val) {
                ans[l] = 'A';
            } else {
                ans[l] = 'B';
            }
        }
        return;
    }
 
    // both sides now
    vector<int> ldp = cur_dp, rdp = cur_dp;
    int m = (l + r) / 2;
    fill_items(ldp, m + 1, r); // right side on left
    f(f, l, m, ldp);
 
    fill_items(rdp, l, m);
    f(f, m + 1, r, rdp);
};

unbounded knapsack

infinite uses of knapsack

trick is to iterate forward from wt(i) till W as this allows you to use “prev” state created via current item