01背包 暴力做法。。。dfs

只能过 6 个，用来练习了一下dfs而已

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

// 物品数量 n, 背包容积 m
int n, m;
int v[N], w[N];
int maxv;

// curv 当前背包的容量，curw当前背包的价值
void dfs(int idx, int curv, int curw) {
    if(idx == n ) {
        maxv = max(curw, maxv);
        return;
    }
    // 不选他
    dfs(idx + 1, curv, curw);

    // 剪枝
    if(curv + v[idx] <= m) { 
        // 选他
        dfs(idx + 1, curv + v[idx], curw + w[idx]);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) {
        cin >> v[i] >> w[i];
    }
    dfs(0, 0, 0);
    cout << maxv;
    return 0;
}