CSES 3. Book Shop (1158)

출처: https://cses.fi/problemset/1158

---

문제 설명

You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

입력 

N X // Number of books, maximum total price

h_i // books price

s_i // number of pages

 

출력

the maximum number of pages.

입력 예 

4 10
4 8 5 3
5 12 8 1

출력 예

13

제약조건

• 1<= N <= 1000
• 1<= X <= 1e5
• 1<= h_i, s_i <= 1000 

---

문제 풀이 내용

Knapsack 문제이다. 어떤 특정한 책을 선택했을 때 페이지와, 그 책을 고르지 않았을 경우에 얻을 수 있는 페이지의 최대값을 비교해서 큰 값을 선택하도록 한다.

프로그램 내용

...
    vector<int> pr(n,0);
    vector<int> pg(n,0);
    vector<int> dp(x+1,0);
...
    for (int i = 0; i < n; i++) 
        for (int j = x; j >= 1; j--) 
            if (pr[i] <= j) 
                dp[j] = max(dp[j], dp[j - pr[i]] + pg[i]); 
...

 

Dynamic Programming ( link )