Patterns

Choose subset of items to maximize value within capacity

When to usePartition equal subset sum, coin change variants, target sum

0/1 Knapsack Practice Problem

knapsack_intro

Efficient Job Processing Service

twitter_oa_efficient_job_processing_service

Coin Change, Optimization

coin_change

Coin Change II

coin_change_ii

Knapsack DP Introduction

Partition to Two Equal Sum Subsets

partition_equal_subset_sum

Perfect Squares 2

perfect_squares_2

Citadel Online Assessment | Ways to Sum | Citadel OA 2022

ways_to_sum

0 1 Knapsackmedium

0_1_knapsack · no slots

DECLARE

dp = new Array(capacity + 1).fill(0)

const dp = new Array(max_weight + 1).fill(0);

const dp = new Array(b + 1).fill(0);

const dp = new Array(amount + 1).fill(Infinity);

const dp = new Array(amount + 1).fill(0);

const dp = new Array(target + 1).fill(false);

const target = total / 2;
const dp = new Array(target + 1).fill(false);

const total = weights.reduce((s, w) => s + w, 0);
const dp = new Array(total + 1).fill(false);

const total = nums.reduce((s, n) => s + n, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
const dp = new Array(target + 1).fill(false);

const squares = [];
for (let i = 1; i * i <= n; i++) squares.push(i * i);
const dp = new Array(n + 1).fill(Infinity);

const MOD = 1000000007n;
const dp = new Array(total + 1).fill(0n);

—

const total = nums.reduce((s, n) => s + n, 0);
if (Math.abs(target) > total) return 0;
if ((total + target) % 2 !== 0) return 0;
const P = (total + target) / 2;
const dp = new Array(P + 1).fill(0);

const expandedWeights = [];
const expandedValues = [];
for (let i = 0; i < weights.length; i++) {
  for (let k = 0; k < counts[i]; k++) {
    expandedWeights.push(weights[i]);
    expandedValues.push(values[i]);
  }
}
const dp = new Array(capacity + 1).fill(0);

BASE CASES

dp[0] = 0 (zero capacity, zero value)

// dp[0] = 0 — covered by fill(0) above

// dp[0..b] = 0 — zero work if no candidates hired

dp[0] = 0;

dp[0] = 1;

dp[0] = true;

dp[0] = true;

dp[0] = true;

dp[0] = true;

dp[0] = 0;

dp[0] = 1n;

—

dp[0] = 1;

// dp[0] = 0 — covered by fill(0) above

BUILD

outer: for each item; inner: for c from capacity down to item.weight

for (let i = 0; i < weights.length; i++) {

for (let i = 0; i < s.length; i++) {

for (const coin of coins) {

for (const coin of coins) {

for (const num of nums) {

for (const n of nums) {

for (const w of weights) {

for (const n of nums) {

for (const sq of squares) {

for (let weight = 1; weight <= k; weight++) {

—

for (const num of nums) {

for (let i = 0; i < expandedWeights.length; i++) {

[RECURRENCE]

dp[c] = Math.max(dp[c], dp[c - weight] + value)

    dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);

    dp[c] = Math.max(dp[c], dp[c - cost] + w[i]);

    dp[i] = Math.min(dp[i], dp[i - coin] + 1);

    dp[i] += dp[i - coin];

    dp[j] = dp[j] || dp[j - num];

    dp[j] = dp[j] || dp[j - n];

    dp[j] = dp[j] || dp[j - w];

    dp[j] = dp[j] || dp[j - n];

    if (dp[j - sq] !== Infinity) dp[j] = Math.min(dp[j], dp[j - sq] + 1);

    dp[j] = (dp[j] + dp[j - weight]) % MOD;

—

    dp[s] += dp[s - num];

    dp[c] = Math.max(dp[c], dp[c - expandedWeights[i]] + expandedValues[i]);

RETURN

return dp[capacity]

return dp[max_weight];

return dp[b];

return dp[amount] === Infinity ? -1 : dp[amount];

return dp[amount];

return dp[target];

return dp[target];

return dp.reduce((acc, v, i) => { if (v) acc.push(i); return acc; }, []);

return dp[target];

return dp[n] === Infinity ? -1 : dp[n];

return Number(dp[total]);

—

return dp[P];

return dp[capacity];