[백준] 12865.cpp : 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

---

• 배낭 문제 , 0/1 Knapsack Problem 과 동일한 유형이다.
• 물건의 갯수를 행으로, 배낭 무게를 0~K 까지 열로 삼은 DP를 활용한다.
• 원래 알고리즘에서는 물건의 갯수를 0~N 까지 전부 배열로 만드는데, 슬라이딩 윈도우 기법을 적용해보았다.
• 이걸 안 찾아보고 혼자서 푸는 사람은 뭐하는 사람일까 싶다..

---

#include <iostream>

using namespace std;

int n, k;
int w, v;
int dp[2][100001];
int answer;

int main(void)
{
    cin >> n >> k;
    for(int i = 0 ; i < n ; i++)
    {
        cin >> w >> v;

        for(int j = 1 ; j <= k ; j++)
        {
            if(j < w) dp[i%2][j] = dp[(i+1)%2][j];                              // 배낭에 들어갈 수 없으면 이전 물건 값 그대로
            else dp[i%2][j] = max(dp[(i+1)%2][j], dp[(i+1)%2][j - w] + v);      // 이전 물건 값과 새롭게 추가한 물건값을 비교해서 더 큰 쪽을 저장
            if(dp[i%2][j] > answer) answer = dp[i%2][j];                        // 최댓값 갱신
        }
    }

    cout << answer << endl;
}