urparvezali's blog

CSES DP Book Shop recursive
By urparvezali, history, 12 months ago, In English

Whenever I try to solve any dp problem it pushes my mind in the way of recursion. I cant think of looping dp but recursion. CSES DP Section problem BOOK SHOP, I tried to solve this but it got TLE 7/15 test cases after using dp vector of vector. how to solve this. As i cant think solving dp problem with iterative method please help me solving it recursively. this is my code below,

#include <bits/stdc++.h>
using namespace std;

int rec(int x, vector<pair<int, int>>& v, vector<vector<int>>& dp, int i, int n) {
    if (i > n - 1) return 0;
    if (dp[i][x] != -1) return dp[i][x];

    int a = rec(x, v, dp, i + 1, n);
    int b = 0;

    if (x - v[i].first >= 0)
        b = v[i].second + rec(x - v[i].first, v, dp, i + 1, n);

    return dp[i][x] = max(a, b);

}

int main() {
    int n, x;
    cin >> n >> x;
    vector<pair<int, int>> v(n);

    for (auto& [i, j] : v) cin >> i;
    for (auto& [i, j] : v) cin >> j;

    vector<vector<int>> dp(n + 1, vector<int>(x + 1, -1));
    
    cout << rec(x, v, dp, 0, n) << endl;
}
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The key to solving DP problems like BOOK SHOP iteratively is to fill up the dp array in a bottom-up fashion instead of using recursive calls.

The iterative approach would be:

Initialize a 2D dp array of size n+1 x x+1. dp[i][j] will represent the max profit with the first i books and a budget of j. Fill up the dp array row-by-row iteratively:

for (int i = 1; i <= n; i++) { for (int j = 0; j <= x; j++) {

// Don't take this book 
dp[i][j] = dp[i-1][j];  

// Take this book if possible
if (j >= v[i].first) {
  dp[i][j] = max(dp[i][j], dp[i-1][j - v[i].first] + v[i].second); 
}

} }

The final answer is in dp[n][x]. This avoids recursion by calculating values in the dp table sequentially. It allows us to pass test cases in O(nx) memory.

Of course, it requires a bit of shift in thinking compared to a recursive approach. But with practice, iterative starts becoming more intuitive for DP problems.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it 
    for (int i = 1; i <= n; i++) {
  for (int j = 0; j <= x; j++) {
    
    // Don't take this book 
    dp[i][j] = dp[i-1][j];  

    // Take this book if possible
    if (j >= v[i].first) {
      dp[i][j] = max(dp[i][j], dp[i-1][j - v[i].first] + v[i].second); 
    }
  }
}
    → Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is a case of the classical problem called 0-1 knapsack.

dp[i][x] = maximum number of pages we can get for price at most x, only buying among the first i books.

Initially dp[0][x] = 0 for all x, as we can't get any pages without any books.

When calculating dp[i][x], we look at the last considered book, the i'th book. We either didn't buy it, leaving x money for the first i-1 books, giving dp[i-1][x] pages. Or we bought it, leaving x-price[i-1] money for the other i-1 books, and giving pages[i-1] extra pages from the bought book. Thus, buying the i'th book gives dp[i-1][x-price[i-1]] + pages[i-1] pages.

The complexity is O(n⋅x)

CODE:

vector<vector> dp(n + 1, vector(x + 1, 0)); for (int i = 1; i <= n; i++) {

for (int j = 0; j <= x; j++)
    {

        dp[i][j] = dp[i-1][j];

        int left = j -price[i-1];

        if (left >= 0)
        {

            dp[i][j] = max(dp[i][j], dp[i-1][left] + pages[i-1]);

        }}}

cout << dp[n][x] <<nl;
→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
import sys
n, x = map(int, input().split())
prices = list(map(int, input().split()))
pages = list(map(int, input().split()))
dp = [0] * (x + 1)
for i in range(n):
    price = prices[i]
    page = pages[i]
    for j in range(x, price - 1, -1):
        dp[j] = max(dp[j], dp[j - price] + page)
print(dp[x])

Space optimized dp solution

→ Reply