[백준 c++] 12865 평범한 배낭

문제

https://www.acmicpc.net/problem/12865
배낭에는 무게 k만큼 담을 수 있다.
n개의 물건은 각각 무게 w와 가치 v를 가진다.
배낭에 넣을 수 있는 최대 가치를 구하는 문제다.

풀이

완전탐색 dp문제다.
물건의 무게와 가치를 입력받을 때마다 k~w 범위를 순회하면서 dp를 max값으로 바꿔주면 된다.

단, 여기서 주의해야할 것은 각 물건은 중복해서 넣을 수 없다는 것이다.
처음 풀 때 물건 값 입력받고 dp 순회하는 범위를 w~k로 잡았더니 중복이 발생했다. 따라서 dp 순회하는 범위를 k~w(역순)으로 설정해야한다.

코드

#include <iostream>
using namespace std;
int n, k, w, v, dp[100001], res;

int main()
{
    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        cin >> w >> v;
        for (int j = k; j >= w; j--)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
    cout << dp[k] << "\n";
}