Project L
  • Preface
  • Part 1
    • Introduction
    • Before We Begin
      • Pythonic things
    • Basic Data Structures
      • Array and String
        • Math
          • Plus One
          • Move Zeroes
          • Rotate Matrix
          • Sparse Matrix Multiplication
          • Missing Numbers
          • Find All Numbers Disappeared in an Array
          • Drop Eggs
        • Sorted Array
          • Median of Two Sorted Arrays
          • Two to K Sum
        • Unsorted Array
          • Partition Array
          • Kth Largest Element
          • Sort Colors
        • Subarray
          • Maximum Subarray
        • Two Pointers
          • L/R Pointers
            • Reverse String
            • Valid Palindrome
            • Trapping Rain Water
          • F/S Pointers
          • P1/P2 Pointers
            • Implement strStr()
            • Intersection of Two Arrays
            • Merge Two Sorted Arrays
          • Window
            • Window Sum
            • Minimum Size Subarray Sum
            • Longest Substring Without Repeating Characters
            • Minimum Window Substring
            • Longest Substring with At Most K Distinct Characters
        • String Builder
          • Reverse Words in a String
        • Rotated Array
      • Hashing
        • Hash Function
        • Group Anagrams
        • Rolling Hash
        • LSH
        • Hash Heap
      • Linked List
        • Singly Linked List
          • Plus One Linked List
          • Partition List
          • Rotate List
          • Palindrome Linked List
          • Reverse Nodes in k-Group
          • Insertion Sort List
          • Sort List
          • Merge K Sorted Lists
          • Copy List with Random Pointer
        • Doubly Linked List
          • BST To DLL
          • LRU Cache
        • Circular Linked List
          • Insert into a Cyclic Sorted List
      • Stack
        • Valid Parenthesis
        • Min Stack
        • 📊Next Greater Element I
        • 🏙️Largest Rectangle in Histogram
      • Queue
        • Moving Average from Data Stream
        • Double-ended Queue
          • Sliding Window Maximum
      • Binary Tree
        • Tree Traversal
          • Binary Tree Paths
          • Binary Tree Path Sum
          • Iterative
            • Flatten List Iterator
            • Flatten Nested List Iterator
            • Flatten 2D Vector
            • Binary Tree to Linked List
            • Zigzag Iterator
        • Divide and Conquer
          • Subtree Max Avg
          • Max Depth of Binary Tree
          • Balanced Binary Tree
          • Lowest Common Ancestor
          • Longest Univalue Path
          • Binary Tree Maximum Path Sum
          • Binary Tree Leaves
        • Binary Search Tree
          • Search in a Binary Search Tree
          • Insert into a Binary Search Tree
          • Delete Node in a BST
          • Binary Search Tree Iterator
          • Convert Binary Search Tree to Sorted Doubly Linked List
          • Convert Sorted Array to Binary Search Tree
          • Convert Sorted List to Binary Search Tree
          • Search Range in Binary Search Tree
          • LCA in BST
          • Validate BST
          • Kth Smallest Element in a BST
        • BFS
          • Binary Tree Level Order Traversal
          • Binary Tree Vertical Order Traversal
          • Binary Tree Serialization
      • Priority Queue
        • Top K Largest Numbers
        • Top K Frequent Elements
        • K Closest Points
        • Kth Smallest Element in a Sorted Matrix
        • Find Median from Data Stream
        • Ugly Number
        • Merge K Sorted Arrays
        • Sliding Window Median
        • 🧵Reorganize String
  • Part 2
    • Divide and Conquer
      • Recursion
        • Recurrence
      • Binary Search
        • Search First/Last Position
        • Search Insert Position
        • Find Closest Number in a Sorted Array
        • First Bad Version
        • Search in a Big Sorted Array
        • Search for a Range
        • Search a 2D Matrix
        • Search a 2D Matrix II
        • Find Trough/Peak Element
        • Search in Rotated Sorted Array
          • Find Minimum in Rotated Sorted Array
        • Recover RSA
        • Square Root
      • Sorting
        • Bubble Sort
        • Selection Sort
        • Insertion Sort
        • Merge Sort
        • Quick Sort
        • Heap Sort
    • Graph Search
      • Search in a Grid
        • Shortest Knight Path
        • Number of Islands
        • Word Search
        • The Maze
        • Shortest Path in a Changing Maze
        • Walls and Gates
      • Exhaustive Search
        • Subsets
        • Partition to K Equal Sum Subsets
        • Combinations
        • Combination Sum
        • Factor Combinations
        • Letter Combinations of a Phone Number
        • Nested List Weight Sum
        • Generate Parentheses
        • Permutations
        • Next Permutation
          • Iterator for Combination
        • N-Queen
        • 8 Puzzle
      • Graph Theory
        • Graph Data Structure
          • Search Nearest Target Node
          • Six Degrees
          • Graph Valid Tree
          • Clone Graph
        • Graph Traversal
          • Word Ladder
          • Word Ladder II
          • Sliding Puzzle
        • Topological Sort
          • Course Schedule
          • Alien Dictionary
          • Cycle Detection
        • Connected Component
          • Strongly Connected Components
          • Number of Islands II
        • Bipartite Graph
          • Is the Graph Bipartite?
        • Subgraph Matching
    • Greedy Algorithm
      • Longest Palindrome
      • Meeting Rooms
      • Merge Intervals
      • Non-overlapping Intervals
      • 🚰Minimum Number of Taps to Open to Water a Garden
      • Minimum Spanning Tree
      • CPU Task Scheduling
      • Teemo Attacking
    • Dynamic Programming
      • Coordinate DP
        • Fibonacci Numbers
        • Climbing Stairs
        • House Robber
        • Unique Paths
        • Longest Increasing Subsequence
        • Minimum Path Sum
        • Manhattan's Map
        • Maximal Square
        • Jump Game
        • Frog Jump
      • Single Sequence DP
        • Paint Fence
        • Wood Cut
        • Rod Cutting
        • Word Break
        • Longest Palindromic Subsequence
        • Maximum Profit in Job Scheduling
        • Russian Doll Envelopes
      • Double Sequence DP
        • Longest Common Subsequence
        • Edit Distance
        • Regex Matching
        • Wildcard Matching
        • Interleaving String
      • Partition DP
        • Best Time to Buy and Sell Stock
        • Word Break
        • Text Justification
        • Decode Ways
      • Substring DP
        • Longest Palindromic Substring
        • Scramble String
        • Parenthesis Correction
        • Matrix Multiplication Parenthesization
        • Burst Balloons
      • Knapsack
        • 📐Subset Sum
        • 🪙Coin Change
        • Coin Change 2
        • ⏹️Perfect Sqaures
        • 0/1 Knapsack
        • 0/1 Knapsack with Benefits
        • K Sum
        • Combination Sum IV
        • Infinite Knapsack
        • Fractional Knapsack
        • M-d Knapsack
        • Backpack IV
      • Tree DP
        • House Robber III
        • Tree Vertex Cover
        • Longest String Chain
        • K Edit Distance
      • Game DP
        • Blackjack
        • Biased Coins K heads
        • Coins in a Line
        • Stone Game
  • Part 3
    • Advanced Topics
      • Concurrency
        • Coroutine
        • Goroutine
          • Equivalent Binary Trees
        • Mutex
          • Web Crawler
      • Scientific Computing
        • 0 Computer Arithmetic
        • 1 Root Finding
        • 2 Numerical Linear Algebra
        • 3 Least Square Approximation
      • Computational Complexity
        • Asymptotic Analysis
        • NP-completeness
        • Classic NPC Problems
        • Proving Problems NPC
      • Linear Programming
        • Integer Linear Programming
      • Randomized Algorithms
      • Machine Learning
        • Learning Theory
          • Consistency Model
          • PAC Learning Model
          • PAC Examples
          • Unions of Intervals
  • Part 4
    • Advanced Data Structures
      • Set Data
        • Union Find
      • Multidimensional Data
        • Binary Tree
          • K-dimensional Tree
          • Segment Tree
            • Interval Sum
            • Range Sum Query
            • Range Sum Query 2D
            • The Skyline Problem
            • Count of Smaller Numbers After Self
        • Quadtree
          • Point Quadtree
          • Matrix Quadtree
          • Point-Region Quadtree
        • B-tree
          • R-Tree
      • Text Data
        • Prefix Tree
        • Suffix Tree
        • Inverted Index
      • Graph Data
        • Union Find
      • Cache Replacement
        • LRU Cache
        • LFU Cache
  • Part 5
    • System Design
      • Mini Twitter
      • Design TinyURL
      • Object Oriented Design
    • References
Powered by GitBook
On this page
  • Introduction
  • Types
  • References
  1. Part 2
  2. Dynamic Programming

Knapsack

PreviousBurst BalloonsNextSubset Sum

Last updated 5 years ago

Introduction

Knapsack problems are perfect illustrations of the spirit of dynamic programming. Optimization problems => optimal substructures. And the constraints and the price table will usually give some overlapping recursive calls.

Types

  • 0/1 Knapsack (size)

    • doability

    • number of ways

    • subsets

  • 0/1 Knapsack (size and value)

  • Multi-constraint Knapsack

  • Combination Knapsack

  • Infinite Knapsack

References

  • Wikipedia -

  • Wikipedia -

  • by linspiration

  • by Tianyi Cui

Knapsack Problem
Continuous knapsack problem
Backpack I to VI
9 lessons on pack