(SWEA c++)5215. 햄버거 다이어트

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE

SW Expert Academy

 

DP 문제 중 0/1 Knapsack 문제와 같다.

아래 링크에 상세한 설명이 있으니 참고!

eunchanee.tistory.com/169

(SWEA c++)3282. 0/1 Knapsack

 

#include <iostream>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        int N, L;
        int dp[21][10001];
        int w[21], v[21];
        
        cin >> N >> L;
        
        for(int i = 1; i <= N; i++)
            cin >> v[i] >> w[i];
        
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= L; j++)
            {
                if(w[i] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = v[i] + dp[i - 1][j - w[i]] > dp[i -1][j] ? v[i] + dp[i - 1][j - w[i]] : dp[i -1][j];
            }
        }
        cout << "#" << tc << " " << dp[N][L] << endl;
    }
    return 0;
}