c++:实现0-1背包问题的回溯算法

以下是C++实现0-1背包问题的回溯算法示例：

#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapSack(int W, int wt[], int val[], int n) {
    if (n == 0 || W == 0) {
        return 0;
    }
    if (wt[n - 1] > W) {
        return knapSack(W, wt, val, n - 1);
    } else {
        return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
    }
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    cout << "Maximum value that can be obtained is " << knapSack(W, wt, val, n);
    return 0;
}

相关问题

0-1背包问题 回溯算法c++

0-1背包问题是计算机科学中的一个经典动态规划问题，它涉及到在给定的一组物品中选择一些放入容量有限的背包，使得这些物品的总价值最大，每种物品只能取一次。这个问题可以用回溯算法求解，特别是当物品有无限多种可能性时。

在C++中，解决0-1背包问题的回溯算法通常包括以下几个步骤：
1. 定义状态：用二维数组dp[i][j]表示前i件物品在容量为j的情况下能得到的最大价值。
2. 初始化：dp[0][j] = 0，表示没有物品时背包的价值为0；对于每个物品，dp[i][0] = val[i]，表示单件物品的价值。
3. 动态规划：遍历所有物品和背包容量，如果当前物品可以放入背包（即其重量小于等于剩余容量），则更新dp[i][j]为当前物品价值加上dp[i-1][j-w[i]]（w[i]为第i个物品的重量），否则dp[i][j] = dp[i-1][j]。
4. 回溯：当达到某个时刻，如果背包已满但仍有一个未考虑的物品，则说明当前路径不合适，需要回溯到上一步，尝试其他物品组合。

下面是简化的伪代码示例：

bool chooseItem(int i, int w[], int j, vector<int>& val, vector<vector<int>>& dp) {
    if (j < w[i]) // 当物品放不下时
        return false;
    else {
        dp[i][j] = max(dp[i][j], val[i] + dp[i - 1][j - w[i]]); // 更新dp值
        return true; // 继续尝试其他物品
    }
}

vector<int> knapsack(int w[], int val[], int n, int W) {
    vector<vector<int>> dp(n+1, vector<int>(W+1));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= W; ++j)
            chooseItem(i, w, j, val, dp);
    return dp[n][W];
}

用c++实现0-1背包问题的回溯算法和分支限界算法

回溯算法实现0-1背包问题：

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

int n, c;
int w[100], v[100];
int ans;

void dfs(int idx, int cw, int cv) {
    if (idx == n) {
        if (cw <= c) ans = max(ans, cv);
        return;
    }
    dfs(idx + 1, cw, cv); // 不选第idx个物品
    if (cw + w[idx] <= c) dfs(idx + 1, cw + w[idx], cv + v[idx]); // 选第idx个物品
}

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

分支限界算法实现0-1背包问题：

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

struct Node {
    int idx, cw, cv; // 物品编号，当前重量，当前价值
    double ub; // 上界
    bool operator < (const Node& other) const {
        return ub < other.ub;
    }
};

int n, c;
int w[100], v[100];
int ans;

double calcUb(int idx, int cw, int cv) {
    double ub = cv;
    int leftW = c - cw;
    while (idx < n && leftW >= w[idx]) {
        ub += v[idx];
        leftW -= w[idx];
        idx++;
    }
    if (idx < n) ub += (double)v[idx] / w[idx] * leftW;
    return ub;
}

void branchBound() {
    priority_queue<Node> pq;
    pq.push({0, 0, 0, calcUb(0, 0, 0)});
    while (!pq.empty()) {
        Node node = pq.top();
        pq.pop();
        if (node.idx == n) {
            ans = max(ans, node.cv);
            continue;
        }
        if (node.ub <= ans) continue; // 如果当前上界小于等于已知最优解，则不再扩展
        pq.push({node.idx + 1, node.cw, node.cv, calcUb(node.idx + 1, node.cw, node.cv)});
        if (node.cw + w[node.idx] <= c) {
            pq.push({node.idx + 1, node.cw + w[node.idx], node.cv + v[node.idx], calcUb(node.idx + 1, node.cw + w[node.idx], node.cv + v[node.idx])});
        }
    }
}

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