12865번 평범한 배낭

 DP 문제.

 

	1	2	3	4	5	6	7
6,13	0	0	0	0	0	13	13
4,8	0	0	0	8	8	13	13
3,6	0	0	6	8	8	13	14
5,12	0	0	6	8	12	13	14

 테이블을 그려서 직접 하나씩 넣어가면서 생각해보면 점화식이 쉽게 나온다.

 (1부터 7은 배낭에 들어갈 수 있는 용량을 의미하고 맨 왼쪽 열에 적혀있는 두 숫자들은 무게와 가치를 의미한다)

 

 i) k-무게[i]가 0과 같거나 크다면,

      dp[i][k]=max(dp[i-1][k],dp[i-1][k-무게[i]] + 가치[i]) 

 ii) 0보다 작다면,

      dp[i][k]=dp[i-1][k]

 

 

#include <iostream>
#define col 100001
#define row 101
 
using namespace std;
 
int dp[row][col];
int WV[row][2];
int N,K;
int W,V;
 
void solved(){
    for(int i=0;i<N;i++){
        W=WV[i][0];
        V=WV[i][1];
        for(int j=0;j<=K;j++){
            if(j-W>=0){
                dp[i+1][j]=max(dp[i][j],dp[i][j-W]+V);
            }
            else{
                dp[i+1][j]=dp[i][j];
            }
        }
    }
    
    cout << dp[N][K];
}
 
int main() {
    cin >> N >> K;
    
    for(int i=0;i<N;i++){
        cin >> WV[i][0] >> WV[i][1];
    }
    
    solved();
}