💻
Algorithm
  • README
  • Array
    • At Most To Equal
    • Count Inversions In An Array
    • Interleaving Placement
    • Kadane
    • Left To Right State Transition
    • Permutation
    • Quick Select
    • Sliding Window
    • Two Pointers
  • Binary Tree
    • Avl Tree
    • Binary Search Tree
    • Serialization And Deserialization
    • Traversal
  • Company
    • Facebook
  • Cpp
    • Array
    • Memset 3 F
    • Overflow
  • Data Structure
    • Binary Indexed Tree
    • Segment Tree And Binary Index Tree
    • Segment Tree
    • Stack
    • Trie
    • Union Find
  • Dynamic Programming
    • Knapsack
      • 0 1 Knapsack
      • Bounded Knapsack
      • Unbounded Knapsack
    • Bitmask Dp
    • Dp On Subsets
    • Dp On Tree
    • Dp With Sorting
    • Selective State Dp
    • Travelling Salesperson
  • Graph
    • Minimum Spanning Tree
      • Kruskal
      • Prim
    • Shortest Path
      • Bellman Ford
      • Dijkstra
      • Floyd Warshall
      • Johnson
      • Shortest Path Faster Algorithm
    • Bi Directional Breadth First Search
    • Bipartite
    • Breadth First Search
    • Component Coloring
    • Component Count
    • Depth First Search
    • Eulerian Path
    • Maximum Bipartite Matching
    • Tarjan
    • Topological Sort
    • Tree Diameter
    • Tree Ring Order Traversal
  • Greedy
    • Greedy Scheduling
    • Regret Greedy
  • Math
    • Catalan Number
    • Combinatorics
    • Factorial
    • Factorization
    • Fast Pow
    • Gcd
    • Geometry
    • Get Digits
    • Lcm
    • Median Minimizes Sum Of Absolute Deviations
    • Mode
    • Modular Multiplicative Inverse
    • Palindrome
    • Prime Number
    • Round Up
    • Sieve Of Eratosthenes
    • Stars And Bars
    • Sum Of Sequence
  • Miscellaneous
    • Bin Packing
    • Floyds Tortoise And Hare
    • Hungarian
    • Palindrome
  • Sort
    • Bubble Sort
    • Cycle Sort
    • Heap Sort
    • Merge Sort
    • Quick Sort
    • Sorting
  • Stl
    • Cpp Stl
    • Istringstream
    • Lower Bound Upper Bound
    • Priority Queue
  • String
    • Kmp
    • Manacher
    • Rabin Karp
    • String Processing
    • Z
  • Backtracking
  • Binary Answer
  • Binary Lifting
  • Binary Search
  • Bit Manipulation
  • Date
  • Difference Array
  • Discretization
  • Divide And Conquer
  • Gray Code
  • Great Problems For Practice
  • Interval Scheduling Maximization
  • Io Optimization
  • K Subset Partitioning
  • Line Sweep
  • Longest Common Subsequence
  • Longest Increasing Subsequence
  • Meet In The Middle
  • Minmax
  • Mono Deque
  • Monotonic Stack
  • Offline Query
  • P And Np
  • Prefix State Map
  • Prefix Sum
  • Random
  • Reservoir Sampling
  • Reverse Polish Notation
  • Sqrt Decomposition
Powered by GitBook
On this page
  • Algorithm
  • Implementation
  • Space Optimization
  • A Constant Optimization
  • Problems

Was this helpful?

  1. Dynamic Programming
  2. Knapsack

0 1 Knapsack

Given a list of items with weight w[i] and value v[i], what's the maximum value you can get given a knapsack with capacity C, i.e. it can hold items with at most weight C in total. You can pick each item at most once (i.e. either pick an item i 0 times or 1 time).

Algorithm

Let dp[i + 1][c] be the maximum value we can get using the first i + 1 items (index from 0 to i) and weight capped by c.

dp[i + 1][c] = max(
    dp[i][c],             // If we skip `i`-th item
    dp[i][c-w[i]] + v[i]  // If we pick `i`-th item
)

dp[0][c] = 0

Implementation

// Time: O(NC)
// Space: O(NC)
vector<vector<int>> dp(N + 1, vector<int>(C + 1));
for (int i = 0; i < N; ++i) {
    for (int c = w[i]; c <= C; ++c) {
        dp[i + 1][c] = max( dp[i][c], dp[i][c - w[i]] + v[i] );
    }
}
return dp[N][C];

Space Optimization

// Time: O(NC)
// Space: O(C)
vector<int> dp(C + 1);
for (int i = 0; i < N; ++i) {
    for (int c = C; c >= w[i]; --c) {
        dp[c] = max( dp[c], dp[c - w[i]] + v[i] );
    }
}
return dp[C];

A Constant Optimization

Since we only need dp[N][C], which only requires dp[N-1][C] and dp[N-1][C-w[N-1]]. So for i = N - 2 (the second from the last item), we only need to loop from max( w[N-2], C - w[N-1] ) to C.

dp[N-1][C-w[N-1]] requires dp[N-2][C] and dp[N-2][C-w[N-1]-w[N-2]], so for i = N - 3, we only need to loop from max( w[N-3], C - w[N-1] - w[N-2] ) to C.

Generalization: for i-th item, the inner loop should be from max( w[i], C - sum(w[j] | i < j < N ) ) to C.

// Time: O(NC)
// Space: O(C)
vector<int> dp(C + 1);
int sum = accumulate(w.begin(), w.end(), 0);
for (int i = 0; i < N; ++i) {
    sum -= w[i];
    for (int c = C; c >= max(w[i], C - sum); --c) {
        dp[c] = max( dp[c], dp[c - w[i]] + v[i] );
    }
}
return dp[C];

Problems

PreviousKnapsackNextBounded Knapsack

Last updated 1 year ago

Was this helpful?

416. Partition Equal Subset Sum (Medium)
474. Ones and Zeroes (Medium)
494. Target Sum (Medium)