DSA sheet / Dynamic programming
Book Shop
Do these first: Minimizing Coins
The problem in brief
A shop has n books (n up to 1000). Book i has a price and a number of pages. You can buy each book at most once and have a budget x (up to 100 000). Print the maximum total number of pages you can get without exceeding the budget.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1158.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
For each book there is a binary decision. Brute force over all subsets is 2^n, hopeless at n = 1000. What do different subsets have in common that you could share?
-
What matters about a partial choice is only two numbers: money spent and pages collected. Define the best pages you can get with a given budget using only the first i books.
-
Take book i. Either skip it (the answer is the same as with i - 1 books) or take it (you pay its price, you gain its pages, and the rest comes from i - 1 books). Write that as a max.
-
You can drop the book dimension by reusing a single array over budgets, but then the order in which you iterate budgets matters. Which direction avoids using a book twice?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
This is the 0/1 knapsack: each item is taken or left. Exponential search is replaced by a DP whose state is (items considered so far, money available) and whose value is the best pages. The transition is a choice: skip the item, or take it. dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - price_i] + pages_i).
Notice that dp[i] depends only on dp[i - 1], so one array over w suffices, as long as you update it in an order that lets each item be used at most once. If you iterate w upward, dp[w - price] might already include book i, effectively allowing it to be bought many times (that is unbounded knapsack, the coin-change pattern from earlier). Iterating w downward guarantees dp[w - price] still describes the state before book i. The upward/downward choice is the difference between “unlimited copies” and “at most once”.
Intuition
Keep a table “best pages if I have w rupees to spend”. For each new book, walk the table from the richest budget down to the cheapest, and whenever buying this book improves what you could get with that budget, update it. Going from the rich end guarantees you never buy the same book twice in one pass.
Approach
- dp[w] = 0 for all w from 0 to x (with no books, spending nothing gives no pages; it is fine to leave leftover money).
- For each book (price p, pages s): for w from x down to p: dp[w] = max(dp[w], dp[w - p] + s).
- Print dp[x].
Pitfalls: iterate w downward; totals are at most 1000 books * pages up to 1000 = 10^6, which fits in 32-bit; work is n * x = up to 10^8.
Complexity
O(n * x) time, O(x) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
scanf("%d %d", &n, &x);
vector<int> price(n), pages(n);
for (auto &p : price) scanf("%d", &p);
for (auto &s : pages) scanf("%d", &s);
vector<int> dp(x + 1, 0);
for (int i = 0; i < n; i++) {
for (int w = x; w >= price[i]; w--) {
dp[w] = max(dp[w], dp[w - price[i]] + pages[i]);
}
}
printf("%d\n", dp[x]);
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
price = list(map(int, data[2:2 + n]))
pages = list(map(int, data[2 + n:2 + 2 * n]))
dp = [0] * (x + 1)
for i in range(n):
p, s = price[i], pages[i]
for w in range(x, p - 1, -1):
v = dp[w - p] + s
if v > dp[w]:
dp[w] = v
print(dp[x])
main() # heavy at the maximum limits: submit as PyPy 3 on judges that have itimport java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int x = (int) st.nval;
int[] price = new int[n];
int[] pages = new int[n];
for (int i = 0; i < n; i++) {
st.nextToken();
price[i] = (int) st.nval;
}
for (int i = 0; i < n; i++) {
st.nextToken();
pages[i] = (int) st.nval;
}
int[] dp = new int[x + 1];
for (int i = 0; i < n; i++) {
for (int w = x; w >= price[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - price[i]] + pages[i]);
}
}
System.out.println(dp[x]);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const x = data[1];
const price = data.slice(2, 2 + n);
const pages = data.slice(2 + n, 2 + 2 * n);
const dp = new Int32Array(x + 1);
for (let i = 0; i < n; i++) {
const p = price[i];
const s = pages[i];
for (let w = x; w >= p; w--) {
const v = dp[w - p] + s;
if (v > dp[w]) dp[w] = v;
}
}
console.log(dp[x]);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).