[백준] 12865 평범한 배낭

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

12865번: 평범한 배낭

greedy?

예시... 그리디 반례

DP

점화식

[input]

4 7

6 13
4 8
3 6
5 12
---------------------------
[output]


d[item][weight] : 배낭에 넣은 물품의 무게 합이 weight 일때 얻을 수 있는 최대 가치
item/weight
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 14
0 0 0 6 8 12 13 14

14

#include <iostream>
#include <algorithm>

using namespace std;

int n,k;
int w[110];
int v[110];
int dp[110][100010];

int main() {

  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++) // item
      for(int j=0; j<=k; j++) { // weight
          if (j < w[i])
             dp[i][j] = dp[i-1][j];
          else
             dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
      }

  printf("%d\n", dp[n][k]);
}