01背包问题的子集树搜索

如题：

经典01背包问题，直接代码反映心路历程。

//
// Created by _thinkPad on 2023/10/16.
//
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

/*
 * 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
 * 接下来有 N行，每行两个整数 vi,wi，用空格隔开
 * 分别表示第 i 件物品的体积和价值。
 */

// 尝试一下bfs，十分滴粗糙
void s0() {
    int N, V;
    cin >> N >> V;
    vector<int> v, w;
    for (int i = 0; i < N; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        v.push_back(t1);
        w.push_back(t2);
    }
    int i = 0;
    queue<int> qt;
    queue<pair<int, int>> qvw;
    qt.push(i);
    qvw.emplace(V, 0);
    int res = 0;
    while (!qt.empty()) {
        i = qt.front();
        pair<int, int> tvw = qvw.front();
        qvw.pop();
        qt.pop();
        if (tvw.second >= res)
            res = tvw.second;
        if (i == N)
            continue;
        if (tvw.first >= v[i]) {
            qt.push(i + 1);
            qvw.emplace(tvw.first - v[i], tvw.second + w[i]);
        }
        qt.push(i + 1);
        qvw.emplace(tvw.first, tvw.second);

    }
    cout << res << endl;

}

// 暴力bfs超时，进行剪枝优化一下，使用一个sum对未来最大进行预判
void s1() {
    int N, V;
    cin >> N >> V;
    vector<int> v, w, sum;
    for (int i = 0; i < N; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        v.push_back(t1);
        w.push_back(t2);
        sum.push_back(t2);
    }
    for (int i = N - 2; i >= 0; i--) {
        sum[i] += sum[i + 1];
    }
    int i = 0, vi = V, wi = 0, sumi = sum[0];
    queue<int> qi, qv, qw, qsum;
    qi.push(i);
    qv.push(vi);
    qw.push(wi);
    qsum.push(sumi);


    int res = 0;
    while (!qi.empty()) {
        i = qi.front(), vi = qv.front(), wi = qw.front(), sumi = qsum.front();
        qi.pop(), qv.pop(), qw.pop(), qsum.pop();
        if (wi >= res)
            res = wi;
        if (res >= sumi + wi)
            continue;
        if (i == N)
            continue;
        if (vi >= v[i]) {
            qi.push(i + 1);
            qv.push(vi - v[i]);
            qw.push(wi + w[i]);
            qsum.push(sum[i + 1]);
        }
        qi.push(i + 1);
        qv.push(vi);
        qw.push(wi);
        qsum.push(sum[i + 1]);

    }
    cout << res << endl;

}

// 使用限界函数还是失败了（优化了200ms），水一个dfs（就是把queue换stack哈哈哈哈哈）
void s2() {
    int N, V;
    cin >> N >> V;
    vector<int> v, w, sum;
    for (int i = 0; i < N; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        v.push_back(t1);
        w.push_back(t2);
        sum.push_back(t2);
    }
    for (int i = N - 2; i >= 0; i--) {
        sum[i] += sum[i + 1];
    }
    int i = 0, vi = V, wi = 0, sumi = sum[0];
    stack<int> qi, qv, qw, qsum;
    qi.push(i);
    qv.push(vi);
    qw.push(wi);
    qsum.push(sumi);


    int res = 0;
    while (!qi.empty()) {
        i = qi.top(), vi = qv.top(), wi = qw.top(), sumi = qsum.top();
        qi.pop(), qv.pop(), qw.pop(), qsum.pop();
        if (wi >= res)
            res = wi;
        if (res >= sumi + wi)
            continue;
        if (i == N)
            continue;
        if (vi >= v[i]) {
            qi.push(i + 1);
            qv.push(vi - v[i]);
            qw.push(wi + w[i]);
            qsum.push(sum[i + 1]);
        }
        qi.push(i + 1);
        qv.push(vi);
        qw.push(wi);
        qsum.push(sum[i + 1]);

    }
    cout << res << endl;
}

// dfs很显然也是不行的，本质上和bfs差不多，整一个优先队列试试
// 就是按照可以分割物品进行横刀阔斧的剪枝
// 不过优先队列剪枝过程太麻烦了，还需要排序
// 为了方便定义一个类记录状态和排序
class bestQu {
public:
    int v, w;
    float preW;

    explicit bestQu(int vv = 0, int ww = 0) {
        v = vv, w = ww;
        preW = (float) ww / vv;
    }

    bool operator>(bestQu c) const {
        return (double(w) / v) > (double(c.w) / c.v);
    }

    bool operator<(bestQu c) const {
        return (double(w) / v) < (double(c.w) / c.v);
    }

    bool operator==(bestQu c) const {
        return (w == c.w && v == c.v);
    }

    void print() {
        cout << "体积: " << v << " 价值: " << w << " 单位体积价值: " << preW << endl;
    }

    static inline void getBestP(int &bestp, const vector<bestQu> &VW, int V, int i) {
        bestp = 0;
        for (int j = i; j < VW.size(); j++) {
            if (V > 0) {
                if (V >= VW[i].v) {
                    V -= VW[i].v;
                    bestp += VW[i].w;
                } else {
                    // bestp += (int) VW[i].preW * V;
                    bestp += (int) (VW[i].preW * V);// 这里这个（int）强制转换一定要把后面括起来，要不然边界会出问题
                    V = 0;
                }

            } else {
                break;
            }
        }
    }

};


void s3() {
    int N, V;
    cin >> N >> V;
    vector<bestQu> VW;
    int bestp;
    for (int i = 0; i < N; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        VW.emplace_back(t1, t2);
    }
    sort(VW.rbegin(), VW.rend());
    bestQu::getBestP(bestp, VW, V, 0);

    int i = 0, vi = V, wi = 0;
    queue<int> qi, qv, qw;
    qi.push(i);
    qv.push(vi);
    qw.push(wi);


    int res = 0;
    while (!qi.empty()) {
        i = qi.front(), vi = qv.front(), wi = qw.front();
        bestQu::getBestP(bestp, VW, vi, i);
        qi.pop(), qv.pop(), qw.pop();
        if (wi >= res)
            res = wi;
        if (res >= bestp + wi)
            continue;
        if (i == N)
            continue;
        if (vi >= VW[i].v) {
            qi.push(i + 1);
            qv.push(vi - VW[i].v);
            qw.push(wi + VW[i].w);

        }
        qi.push(i + 1);
        qv.push(vi);
        qw.push(wi);


    }
    cout << res << endl;

}

// 经过不断的改良，搜索法过了

#ifndef test

int main() {
    s3();
    return 0;
}

#endif

s0:1900ms

s1:1700ms

s2:1700ms

s3:1ms