0-1背包问题有多种解法，如动态规划方 法，回溯方法，分枝限界方法等。对于同 一种问题，请参照教材中的算法，给出相 应的c++程序实现。要求：(1)回溯方法；(2) 分枝限界方法。

回溯方法的C++代码实现：

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

const int N = 1010;

int n, m;
int w[N], v[N];
int ans;

void dfs(int u, int sum_w, int sum_v)
{
    if (u == n)
    {
        if (sum_w <= m) ans = max(ans, sum_v);
        return;
    }
    dfs(u + 1, sum_w, sum_v);
    dfs(u + 1, sum_w + w[u], sum_v + v[u]);
}

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

分枝限界方法的C++代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 1010;

struct Node
{
    int u;
    int sum_w, sum_v;
    double bound;
    bool operator< (const Node& t) const
    {
        return bound < t.bound;
    }
};

int n, m;
int w[N], v[N];
int ans;

double calc_bound(int u, int sum_w, int sum_v)
{
    double bound = sum_v;
    for (int i = u; i < n; i++)
    {
        if (sum_w + w[i] <= m) bound += v[i];
        else
        {
            bound += 1.0 * (m - sum_w) / w[i] * v[i];
            break;
        }
    }
    return bound;
}

void bfs()
{
    priority_queue<Node> q;
    q.push({-1, 0, 0, calc_bound(0, 0, 0)});
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        if (t.u == n - 1)
        {
            ans = t.sum_v;
            break;
        }
        if (t.bound < ans) continue;
        int u = t.u + 1;
        if (t.sum_w + w[u - 1] <= m) q.push({u, t.sum_w + w[u - 1], t.sum_v + v[u - 1], calc_bound(u, t.sum_w + w[u - 1], t.sum_v + v[u - 1])});
        q.push({u, t.sum_w, t.sum_v, calc_bound(u, t.sum_w, t.sum_v)});
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    bfs();
    cout << ans << endl;
    return 0;
}