백준 12865번: 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

이 문제를 처음 접했을 떄 가장 떠오른 것은 백트래킹이었다. 아직 다이나믹프로그래밍을 모르는 것 같다...(dp문제 풀 떄마다 좌절감을 느끼는 중..)

아래 코드는 백트래킹으로 푼 코드이다 넘어가도 좋당... 나같은 행동은 하지 마세용.. (시간초과로 틀린 코드)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int k;
int ans;
int temp;
int value;
vector<pair<int,int>> v;
bool check[101];
void dfs(int num,int cnt){
    if(cnt==n){
        return;
    }
    for(int i=num;i<n;i++){
        if(!check[i]&&(temp+v[i].first<=k)){
            check[i]=true;
            value+=v[i].second;
            temp+=v[i].first;
            if(ans<value){
                ans=value;
            }
            dfs(i+1,cnt+1);
            check[i]=false;
            value-=v[i].second;
            temp-=v[i].first;
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        v.push_back(make_pair(a,b));
    }
    dfs(0,0);
    cout<<ans;
}

그럼 이 문제를 푸는 방법은 당연히 dp이고 식부터 말하자면 (이해가 안되면 맨 아래코드부터 보자)

경우의 수:1. 배낭을 넣을 것인가 2.배낭을 안 넣을 것인가 

arr[i][j]=max(arr[i-1][j],arr[i-1][j-w[i]]+v[i]);

이 식이 핵심이다.  i는 몇번쨰 배낭인지 j는 무게,w[i],v[i]는 각각 [i]번째 배낭 무게와 값이다. 난 무게를 조건식으로 풀 생각을 해서 못 푼 거 같다.

정답은 배낭의 무게도 배열에 넣어버리는 것이다. 저 식을 해석 하자면

i번쨰 배낭을 탐색할때 j 무게 인 경우 최선을 구하는 것이다.(i번쨰 배낭을 안넣는게 최선이면 arr[i-1][j] , i번쨰 배낭을 넣는게 최선이면 arr[i-1][j-w[i]]+v[i] 즉 현재 배낭 무게를 뻇을 때 값에다가 현재 배낭 값을 더하는 것이다 (현재 배낭을 넣기 떄문)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,k;
int arr[101][100001];
int w[101];
int v[101];
int main(){
    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=1;j<=k;j++){         //매번 무게별로 최선을 고른다고 가정
            if(j>=w[i]){
                arr[i][j]=max(arr[i-1][j],arr[i-1][j-w[i]]+v[i]);        //현 배낭 선택 한것과 안 한 것중 큰 값 넣기 
            }
            else{
                arr[i][j]=arr[i-1][j];           //배낭 선택을 안했으므로 전에 값 가져오기
            }
        }
    }
    cout << arr[n][k];
    
}

진짜 DP가 익숙해지기 너무 어렵다...평소에 생각하는 회로랑 다르게 흘러가는 거 같다..기계처럼 풀어서 그런듯요..