백준 12865 - 평범한 배낭 (c++)

백준 12865 - 평범한 배낭

문제 링크

생각 및 접근

• 전형적인 냅색 알고리즘이다.
  • 자세한 정보
• dp[i]
  • 현재 배낭의 무게가 i일 때의 최대 가치를 저장
• 배낭에 넣을 수 있는 물건이 중복되지 않으므로, j-for문을 역순으로 체킹하면 중복 없이 확인할 수 있다.

    for(int j = k; j >= w; j--){
        dp[j] = max(dp[j], dp[j - w] + v);
    }

  • k는 가방의 제한 무게, w는 현재 검사하려는 물건의 무게, v는 현재 검사하려는 물건의 가치
  • j-for문
    • j를 k부터 w까지 돌린다. j가 w보다 작은 값을 도는 것은 의미가 없다. 현재 검사하려는 물건의 무게가 w이므로, w 미만의 가방 무게에는 검사하려는 물건이 들어갈 수 없다.
    • dp[j]와 dp[j - w] + v 중 큰 값으로 dp[j]를 업데이트 한다.

코드

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n >> k;
    for(int i = 1; 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];
}

채점 결과