[C언어/knapsack(DP)] 12865 : 평범한 배낭

#include<stdio.h>

int w[101];
int v[101];
int dp[101][100001];

int N,K;

int max(int num1,int num2){
	return num1>=num2?num1:num2;
}
int main(void){
	scanf("%d %d",&N,&K);
	
	for(int i=1;i<=N;i++)
		scanf("%d %d",&w[i],&v[i]);
	
	for(int i=1;i<=N;i++){
		for(int j=1;j<=K;j++){
			if(j-w[i]>=0){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			}
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	printf("%d",dp[N][K]);
	return 0;
}