3282 0/1 Knapsack

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr

d[i][j] = 가방의 크기가 i일 때 j번째 물건까지 담을 수 있는 최대 가치

1. 가방의 크기가 i일 때 j번째 물건을 담을 수 있다면 j번째 물건을 담는 경우와 아닌 경우 중 최대값으로 채운다.

     d[i][j] = max(d[i][j-1],d[i-v[j]][j-1]+c[j])

2. 가방의 크기가 i일 때 j번째 물건을 담을 수 없다면 j-1번째 물건까지 담을 수 있는 최대 가치로 채운다.

     d[i][j] = d[i][j-1]

#include <cstdio>
#include <algorithm>
using namespace std;
 
int t,n,k,v[101],c[101],d[1001][101];
 
int main()
{
    scanf("%d",&t);
    for(int T=1;T<=t;T++)
    {
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d %d",&v[i],&c[i]);
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i>=v[j]) d[i][j]=max(d[i][j-1],d[i-v[j]][j-1]+c[j]);
                else d[i][j]=d[i][j-1];
            }
        }
        printf("#%d %d\n",T,d[k][n]);
    }
    return 0;
}