204. 평범한 배낭

백준

1. Python

• https://claude-u.tistory.com/208

• knapsack[i][j] = max(현재 물건 가치 + knapsack[이전 물건][현재 가방 무게 - 현재 물건 무게], knapsack[이전 물건][현재 가방 무게])

• knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split()) # 개수, 최대 무게
#행: 물건 개수
#열: 무게 1~k까지
bag = [[0] * (k + 1) for _ in range(n + 1)] 
things = [(0,0)]+[tuple(map(int, input().split())) for _ in range(n)]

for i in range(1, n + 1):
    weight = things[i][0] 
    value = things[i][1]
    
    for j in range(1, k + 1):
        if j < weight:
            bag[i][j] = bag[i - 1][j] #weight보다 작으면 위의 값을 그대로 가져온다
        else:
            bag[i][j] = max(value + bag[i - 1][j - weight], bag[i - 1][j])


print(bag[n][k])

2. C++

#include <iostream>

#define MAX 110
using namespace std;
 
int n, k;
int weight[MAX];
int value[MAX];
int bag[MAX][100010];
 

int main(void)
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> weight[i] >> value[i];
    }
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            if (j >= weight[i])    bag[i][j] = max(bag[i - 1][j], bag[i - 1][j - weight[i]] + value[i]);
            else bag[i][j] = bag[i - 1][j];
        }
    }
    cout << bag[n][k] << endl;
 
    return 0;
}




``