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

下面是一个基于C++的01背包问题动态规划的实现示例：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n, C;
    cin >> n >> C;

    vector<int> w(n+1); // 物品重量
    vector<int> v(n+1); // 物品价值
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i];
    }

    vector<int> dp(C+1); // dp数组
    for(int i = 1; i <= n; i++)
    {
        for(int j = C; j >= w[i]; j--)
        {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }

    cout << dp[C] << endl;

    return 0;
}

在上面的代码中，我们使用了vector来存储物品的重量和价值，使用一维数组dp来存储最大价值，并且使用了逆序枚举的方式来更新dp数组，以避免重复选择同一个物品。

相关问题

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

以下是 01背包问题 的动态规划的 C 代码实现：

#include <stdio.h>

#define N 1000
#define W 10000

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

int main() {
    int n, m;
    int w[N], v[N];
    int dp[N][W];

    // 输入物品数量和背包容量
    scanf("%d%d", &n, &m);

    // 输入每个物品的重量和价值
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }

    // 初始化
    for (int i = 0; i <= m; i++) {
        dp[0][i] = 0;
    }

    // 动态规划
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j < w[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }

    // 输出结果
    printf("%d\n", dp[n][m]);

    return 0;
}

其中，`n` 表示物品数量，`m` 表示背包容量，`w[i]` 表示第 `i` 个物品的重量，`v[i]` 表示第 `i` 个物品的价值，`dp[i][j]` 表示在前 `i` 个物品中选择，且背包容量为 `j` 时的最大价值。

01背包问题动态规划c++初学者程序

01背包问题是一个经典的动态规划问题，其解决方法有很多，其中一种比较常见的方法是使用二维数组进行动态规划。下面是一个C++初学者程序的示例：

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

const int MAXN = 1005;
int w[MAXN], v[MAXN], f[MAXN][MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= w[i]; j--) {
            f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+v[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

这个程序使用了一个二维数组f来记录每个状态的最优解，其中f[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。程序中使用了一个双重循环来遍历所有状态，并使用max函数来更新最优解。最后输出f[n][m]即为问题的解。