开荒 U54047.鼠鼠的奖励

U54047.鼠鼠的奖励

#include <iostream>
#include <vector>
using namespace std;

struct Item {
    int v;  // value
    int w;  // weight
};

int cap, n;           // 背包容量, 物品数量
vector<Item> items;   // 物品列表
int sumV = 0;         // 总价值
int maxV = 0;         // 最大价值

// DFS函数：cw-当前重量，cv-当前价值
// svs-已选物品价值总和，rvs-剩余物品价值总和
void dfs(int cw, int cv, int svs, int rvs, int idx) {
    if (cw > cap) return;  // 超重返回
    if (cv > maxV) maxV = cv;  // 更新最大价值
    
    for (int i = idx; i < n; ++i) {
        int v = items[i].v;  // 当前物品价值
        int w = items[i].w;  // 当前物品重量
        
        if (svs == 0) {  // 第一个物品直接选择
            dfs(cw + w, cv + v, svs + v, rvs - v, i + 1);
        } else {
            // 规则判断
            bool r1 = (v * 2 >= rvs) || (v * 2 >= svs);
            bool r2 = (v * 4 <= svs);
            if (r1 || r2) continue;  // 跳过不满足条件的
            
            // 选择当前物品
            dfs(cw + w, cv + v, svs + v, rvs - v, i + 1);
        }
    }
}

int main() {
    cin >> cap >> n;
    items.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> items[i].v >> items[i].w;
        sumV += items[i].v;
    }
    dfs(0, 0, 0, sumV, 0);
    cout << maxV << endl;
    return 0;
}