PrevNext
Not Frequent
 0/21

Knapsack DP

Authors: Nathan Chen, Michael Cao, Benjamin Qi

Contributor: Neo Wang

Problems that can be modeled as filling a limited-size container with items.

Edit This Page

Focus Problem – try your best to solve this problem before continuing!

Tutorial

Resources
CPH

Solves "Minimizing Coins," 0/1 Knapsack

YouTube

Videos for common knapsack variations

Knapsack problems generally involve filling a limited container with a subset of items where we want to count or optimize some quantity associated with the items. Almost every time, you can think of each item as having a positive weight, and the total weight of the items we choose must not exceed the capacity of the container, which is some number. Some variations of knapsack-type problems include:

  • The 0/1 Knapsack problem: Choosing a subset of items such that we maximize their total value and their total weight does not exceed the capacity of the container
  • Finding all the possible total weights that we can achieve from any subset of items such that their total weight does not exceed the capacity of the container (in the chapter of CPH linked above)
  • Counting how many sequences of items will fill the container completely, meaning the total weight is exactly the capacity of the container (the order may or may not matter)

The DP solution to knapsack problems usually has the state keeping track of the capacity of the knapsack, and the transitions involve trying to add an item to the knapsack. In competitive programming, you can expect that classical knapsack problems will be given twists, disguises, and extra state information involved.

Solution - Dice Combinations

Time Complexity: O(N)\mathcal{O}(N)

The problem asks us how many sequences of dice rolls exist such that the sum of the top faces is NN (N≤106N \leq 10^6). To keep up with the knapsack analogy, that means we have infinite numbers of items of weights 11 through 66, and we want to count how many sequences of items exist such that if we put items into the container while following the sequence, the container becomes completely full. Note that the order of the items matters in this problem.

For convenience, let dp[x]\texttt{dp}[x] be the number of sequences of dice rolls that add up to xx. To count how many sequences add up to NN, or in other words, to find dp[N]\texttt{dp}[N], let's look at the last dice roll that brings us up to a total sum of NN.

If the last roll was a 11, then we know there are dp[N−1]\texttt{dp}[N-1] ways to achieve sum NN when the last roll is 11. If the last roll was a 22, then we know there are dp[N−2]\texttt{dp}[N-2] ways to achieve sum NN when the last roll is 22. Continue this logic for all the dice numbers up to 66. Considering all those cases together, we have shown that

dp[N]=dp[N−1]+dp[N−2]+dp[N−3]+dp[N−4]+dp[N−5]+dp[N−6].\texttt{dp}[N] = \texttt{dp}[N-1] + \texttt{dp}[N-2] + \texttt{dp}[N-3] + \texttt{dp}[N-4] + \texttt{dp}[N-5] + \texttt{dp}[N-6].

Apply that same logic we used for dp[N]\texttt{dp}[N] on a general xx:

dp[x]=∑i=16dp[x−i].\texttt{dp}[x] = \sum_{i=1}^6\texttt{dp}[x-i].

Start with the base case that dp[0]=1\texttt{dp}[0] = 1, and then dp[1]\texttt{dp}[1], dp[2]\texttt{dp}[2], dp[3]\texttt{dp}[3], and so on... can be calculated using the recurrence until we find dp[N]\texttt{dp}[N]. Note in the code that we ignore dp[x]\texttt{dp}[x] if x<0x < 0.

C++

#include <bits/stdc++.h>
using namespace std;
long long dp[1000001];
int main() {
int n;
cin >> n;
dp[0] = 1;

Java

import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n;
n = Integer.parseInt(br.readLine());
long dp[] = new long[n + 1];

Python

dp = [1]
for i in range(int(input())):
dp.append(sum(dp[-6:]) % (10**9 + 7))
print(dp[-1])

Problems

General

StatusSourceProblem NameDifficultyTags
CSESVery Easy
Show TagsKnapsack
CSESEasy
Show TagsKnapsack
CSESEasy
Show TagsKnapsack
ACEasy
Show TagsKnapsack
CSESEasy
Show TagsKnapsack
CSESEasy
Show TagsKnapsack
CSESEasy
Show TagsKnapsack
CFEasy
Show TagsKnapsack
NOINormal
Show TagsDP, Knapsack
CSESHard
Show TagsKnapsack

USACO

StatusSourceProblem NameDifficultyTags
GoldEasy
Show TagsDP, Knapsack
GoldHard
Show TagsBinary Search, DP, Knapsack
PlatinumVery Hard
Show TagsKnapsack

NT

Some knapsack problems with number-theoretic twists!

StatusSourceProblem NameDifficultyTags
CFNormal
Show TagsKnapsack
GoldNormal
Show TagsExponentiation, Knapsack
GoldNormal
Show TagsKnapsack, Prime Factorization
POINormal
Show TagsKnapsack, Prime Factorization
TCHard
Show TagsDP
CEOIHard
Show TagsKnapsack, Sorting
PlatinumInsane
Show TagsKnapsack, Prime Factorization

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext