01背包问题c++代码

以下是01背包问题的C++代码示例：

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

const int N = 1010;

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

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
        }

    cout << f[n][m] << endl;

    return 0;
}

该代码使用了动态规划的思想，通过填表的方式求解01背包问题。其中，f[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。具体实现中，我们先将f[i][j]初始化为f[i-1][j]，然后再考虑是否将第i个物品放入背包中，如果可以放入，则更新f[i][j]的值。

相关问题

回溯法01背包问题c++代码

回溯法是解决01背包问题的一种常见方法。具体思路是对于每个物品，选择装入或不装入背包，直到将所有物品都遍历完毕。这种方法需要遍历所有可能的情况，因此时间复杂度较高，但是可以得到最优解。

以下是一个简单的C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

int max_weight = 0; //最大承重量
vector<int> weights; //物品重量
vector<int> values; //物品价值
vector<bool> selected; //是否选中该物品

void backtrack(int curr_weight, int curr_value, int index) {
    if (curr_weight > max_weight) { //超过承重量，直接返回
        return;
    }
    if (index == weights.size()) { //所有物品都遍历完毕
        if (curr_value > max_value) { //更新最大价值
            max_value = curr_value;
        }
        return;
    }
    //不选该物品
    backtrack(curr_weight, curr_value, index + 1);
    //选该物品
    selected[index] = true;
    backtrack(curr_weight + weights[index], curr_value + values[index], index + 1);
    selected[index] = false; //回溯
}

int main() {
    int n; //物品数量
    cin >> n;
    cin >> max_weight;
    for (int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;
        weights.push_back(w);
        values.push_back(v);
        selected.push_back(false);
    }
    backtrack(0, 0, 0);
    cout << max_value << endl;
    return 0;
}

动态规划解决01背包问题c++代码

动态规划是一种常用的解决优化问题的算法思想，而01背包问题是动态规划中的一个经典问题。它的目标是在给定背包容量和一组物品的重量和价值的情况下，选择一些物品放入背包中，使得背包中物品的总价值最大化，同时要保证背包的总重量不超过背包容量。

以下是使用动态规划解决01背包问题的C++代码示例：

#include <iostream>
#include <vector>

using namespace std;

int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (wt[i - 1] <= j) {
                dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int W = 10; // 背包容量
    vector<int> wt = {2, 3, 4, 5}; // 物品重量
    vector<int> val = {3, 4, 5, 6}; // 物品价值
    int n = wt.size(); // 物品数量

    int maxVal = knapsack(W, wt, val, n);
    cout << "背包中物品的最大总价值为：" << maxVal << endl;

    return 0;
}