1차원 dp를 사용할 땐, 중복 갱신에 주의해야 함(경우에 따라 역순으로 갱신할것)

12865번: 평범한 배낭

잘못된 코드(19번째 줄에서 dp[w - weight] 이라서 역순으로 갱신해야 함)

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
 
using namespace std;
typedef pair<int, int> pi;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int N, K; cin >> N >> K;
    vector<pi> vec(N); // {weight, value}
    for(auto&[weight, val]: vec) cin >> weight >> val;
 
    vector<int> dp(K+1, 0);
    for(int i = 0; i < N; i++){
        auto& [weight, val] = vec[i];
        for(int w = weight; w <= K; w++){
            dp[w] = max(dp[w], dp[w-weight]+val);
        }
    }
 
    cout << dp[K] << endl;
 
    return 0;
}cs

올바른 코드

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
 
using namespace std;
typedef pair<int, int> pi;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int N, K; cin >> N >> K;
    vector<pi> vec(N); // {weight, value}
    for(auto&[weight, val]: vec) cin >> weight >> val;
 
    vector<int> dp(K+1, 0);
    for(int i = 0; i < N; i++){
        auto& [weight, val] = vec[i];
        for(int w = K; w >= weight; w--){
            dp[w] = max(dp[w], dp[w-weight]+val);
        }
    }
 
    cout << dp[K] << endl;
 
    return 0;
}cs

반례

2 4 1 1 2 2

 

 

이를 굉장히 잘 설명한 블로그 게시글(https://www.acmicpc.net/problem/2629)
dp의 out edge에 주목해서 코딩하였다.

백준 2629번: 양팔저울 - 냅색(배낭) 문제

이 글에서 빠진 논리가 하나 있는데

1차원 dp에서 이전 dp의 값(현재가 i번째 추를 사용할 때 dp값 갱신이라면 i-1번째 추까지 사용했을 때의 dp값을 의미)을 사용해야 하는데

if(dy[j]) dy[abs(j-chu[i])] = 1 ... ⓐ

으로 갱신할 때, 이전 dp의 값을 사용하는 것이 아닌

if(dy[j]) dy[j+chu[i]] = 1 ... ⓑ

ⓑ 갱신을 거친 dp의 값을 사용해도 답이 올바르게 도출되는지는 설명되어 있지 않다.(왜 가능하지 설명해보자. )

ⓐ, ⓑ의 코드 순서를 바꾸면 답이 틀린다

http://boj.kr/2af6c2bd11b2440f9c010959956dc853