백준 평범한 배낭

문제

N개의 물건 -> 무게 W와 가치 V가 주어진다.

가방에 넣을 수 있는 최대 무게 K가 주어질 때 가방에 넣을 수 있는 최대 가치의 합을 구한다.

해석

행 : 물건을 중복해 추가하며 최대값 저장
열 : 담을 수 있는 최대 배낭 무게 한계

0	0	0	0	0	0	0	0
0	0	0	0	0	0	13	13
0	0	0	0	8	8	13	13
0	0	0	6	8	8	13	13
0	0	0	6	8	12	13	14

점화식 : dp[i][j] = max(dp[i-1][j],dp[i-1]j-v[i].first]+v[i].second)

코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;
vector<pair<int,int> > v;
int dp[101][100001];

int Max(int x,int y){
	return x>y?x:y;
}

int main(){
	int N,K;
	scanf("%d %d",&N,&K);
	int tmp1, tmp2;
	v.push_back(make_pair(0,0));
	for(int i=0;i<N;i++){
		scanf("%d %d",&tmp1,&tmp2);
		v.push_back(make_pair(tmp1,tmp2));
	}
	
	for(int i=1;i<=N;i++){
		for(int j=1;j<=K;j++){
			if(j-v[i].first>=0){
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i].first]+v[i].second);
			}else{
				dp[i][j] = dp[i-1][j];
			}
		}
	}
//	for(int i=0;i<=N;i++){
//		for(int j=0;j<=K;j++){
//			printf("%d ",dp[i][j]);
//		}
//		printf("\n");
//	}
	printf("%d",dp[N][K]);
}