백준 12865 평범한 배낭 c++

백준 평범한 배낭 문제

구현 방법

처음에 그리디로 풀 수 있지 않을까 잠깐 고민하다가 DP로 푸는 것이 낫다고 판단했다.

• 테이블 정의
  d[i] = 최대 무게가 i인 배낭의 최대 가치
  

• 점화식 구현
  -무게가 i인 배낭이 가지는 가치값과 j번째 물건을 넣었을 때의 가치값 사이의 최댓값을 넣어준다.
  -d[i] = max(d[i], d[i-w[j]]+v[j]);
  

중복 문제

dp 테이블을 구성할 때, for문을 1부터 시작하여 버틸 수 있는 무게인 k까지로 설정하여 돌렸는데, 여기서 주어진 물건이 중복되어 값이 갱신되는 문제가 발생했다.
하지만 이 문제에서는 해당 물건을 중복하여 사용할 수 없기 때문에 다른 방법을 찾아야 했다.

2차원 배열을 이용함으로써 이를 해결할 수도 있지만, for문의 시작을 1이 아닌 k부터 시작해서 1까지로 바꿔 돌림으로써 1차원 배열로도 문제를 해결할 수 있었다.

구현

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

int w[102], v[102], d[100002];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for(int i = 1; i <= n; i++) {
        for(int j = k; j >= 1; j--) {
        	// 최대무게값에 들어갈 수 있는 배낭만 넣기
            if(w[i] <= j) {
                d[j] = max(d[j], d[j-w[i]]+v[i]);
            }
        }
    }
    cout << d[k];
}