Solution - Book Shop (CSES)

Explanation

For each book $i$ , we either buy it, spending $h[i]$ to gain $s[i]$ pages, or skip it and gain nothing. This is the 0/1 knapsack problem, with cost $h[i]$ , value $s[i]$ , and capacity $x$ , allowing a DP solution.

Let $dp[i][j]$ be the maximum number of pages obtainable using only the first $i$ books with a budget of at most $j$ . The base case is $dp[0][j] = 0$ for all $j$ , since with no books available, no pages can be obtained regardless of budget.

The transition follows as:

$dp[i][j] = dp[i-1][j]$ by default (skip book $i$ )
if $j \geq h[i]$ , we can instead buy book $i$ , giving $dp[i][j] = \max(dp[i-1][j], dp[i-1][j-h[i]] + s[i])$

The final answer is $dp[n][x]$ .

Optional: 1D Knapsack

Since $dp[i][j]$ only depends on row $i-1$ , we don't need to keep every row around: we can compress the DP into a single 1D array of size $x+1$ , overwriting it in place as we go. For each book $i$ , iterate $j$ from $x$ down to $h[i]$ , updating $dp[j] = \max(dp[j], dp[j-h[i]] + s[i])$ . Going downward matters: it keeps $dp[j-h[i]]$ holding last book's value (row $i-1$ ) when we read it, rather than a value already updated for book $i$ (which would let us buy the same book twice).

Implementation

Time Complexity: $\mathcal{O}(N\cdot X)$

import java.io.*;
import java.util.*;

public class bookShop {
	public static void main(String[] args) throws IOException {
		BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(b.readLine());
		int N = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());

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!

Join Forum

Table of Contents

Table of Contents

Explanation

Implementation

Join the USACO Forum!