3282 0/1 Knapsack

SWEA::3282 0/1 Knapsack

완전탐색을 하여 풀었고, 범위가 벗어나면 리턴을 통해 빠져나오도록 하였다.

#include <stdio.h>
#include <vector>
#define P pair<int,int>
using namespace std;
 
int t, n, k, res;
P d[101];
 
void dfs(int idx, int volume, int weight) {
    if (volume + d[idx].first > k) return;
 
    if (weight+d[idx].second > res) {
        res = weight + d[idx].second;
    }
 
    if (idx == n) return;
    dfs(idx + 1, volume, weight);
    dfs(idx + 1, volume + d[idx].first, weight + d[idx].second);
}
 
int main(){
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d%d", &n, &k);
 
        res = 0;
 
        int x, y;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            d[i] = P(x, y);
        }
 
        for (int i = 0; i < n; i++) {
            dfs(i, 0, 0);
        }
 
        printf("#%d %d", tc, res);
    }
}