动态规划01背包问题c++

下面是动态规划求解01背包问题的C++代码：

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

const int N = 1010;

int n, m;
int v[N], w[N]; // v[i]表示第i个物品的价值，w[i]表示第i个物品的重量
int f[N][N]; // f[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值

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

    memset(f, 0, sizeof f); // 初始化f数组

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = f[i-1][j]; // 不选第i个物品
            if(j >= w[i]) // 能选第i个物品
                f[i][j] = max(f[i][j], f[i-1][j-w[i]] + v[i]);
        }

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

    return 0;
}

其中，时间复杂度为 $O(nm)$，空间复杂度为 $O(nm)$。

相关问题

动态规划解决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;
}

01背包问题动态规划C++

01背包问题是一种经典的动态规划问题，它的目标是在背包容量一定的情况下，选择不同的物品，使得装入背包中的物品总价值最大。C++实现的思路如下：

1.定义一个dp数组，其中dp[i][j]表示容量为j时前i个物品的最大价值。
2.使用for循环遍历每一个物品，再使用另一个for循环遍历每一个容量，通过比较是否将当前物品放入背包中能够获得更大的价值，来更新dp数组中对应位置的值。
3.最后dp[n][V]就是容量为V时前n个物品的最大价值。

以下是C++代码实现：

int knapsack(int V, int n, int* w, int* v) {
    int dp[n + 1][V + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (w[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - w[i - 1]] + v[i - 1]);
            }
        }
    }

    return dp[n][V];
}