[16493] 최대 페이지 수

https://www.acmicpc.net/problem/16493

16493번: 최대 페이지 수

<문제>

하나의 챕터를 중복해서 읽지 않는 문제이므로, 역방향으로 갱신하는 배낭문제로 풀 수 있다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

int n, m, ans, dp[201], w[201], v[201];

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> m;

    int i, j;

    for (i = 0; i < m; i++) cin >> w[i] >> v[i];

    for (i = 0; i < m; i++)

        for (j = n; j >= w[i]; j--) dp[j] = max(dp[j - w[i]] + v[i], dp[j]);

    cout << dp[n];

    return 0;

}