0-1背包问题动态规划法c++

以下是使用动态规划法解决0-1背包问题的C++代码：

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

int main() {
    const int N = 1005;
    int n, m, w[N], v[N], dp[N][N] = {0};
    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 = 1; j <= m; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

其中，dp[i][j]表示前i个物品，容量为j时的最大价值。通过递推，可以得到dp[n][m]即为最终的最大价值。

相关问题

c++实现0-1背包问题动态规划法

0-1背包问题是经典的动态规划问题，可以使用c++来实现。以下是一种基于动态规划的解法：

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

int knapsack(vector<int>& values, vector<int>& weights, int capacity) {
    int n = values.size();
    vector<vector<int>> dp(n+1, vector<int>(capacity+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (weights[i-1] <= j) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][capacity];
}

int main() {
    vector<int> values = {6, 10, 12};
    vector<int> weights = {1, 2, 3};
    int capacity = 5;
    cout << knapsack(values, weights, capacity) << endl;
    return 0;
}

首先定义一个二维的dp数组，其中dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。在枚举每个物品时，分为两种情况：如果当前物品可以放入背包中，则需要考虑将其放入或不放入背包中所能获得的最大价值，即dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])；如果当前物品不能放入背包，则直接继承上一个物品的最大价值，即dp[i][j] = dp[i-1][j]。最后返回dp[n][capacity]即可。

c++实现0-1背包问题动态规划法 可视化效果

为了实现0-1背包问题的动态规划，我们需要先定义一个二维数组dp，其中dp[i][j]表示前i个物品，在背包容量为j的情况下能够获得的最大价值。然后，我们可以按照以下步骤进行动态规划：

1. 初始化dp数组，当背包容量为0时，无论有多少物品，总价值都为0；当没有物品可选时，无论背包容量为多少，总价值也都为0。

2. 对于每个物品i和背包容量j，我们需要判断是否将该物品放入背包。如果放入该物品，则背包容量变为j-w[i]，价值变为dp[i-1][j-w[i]]+v[i]；如果不放入该物品，则背包容量不变，价值变为dp[i-1][j]。因此，我们可以取这两种情况中的较大值作为dp[i][j]的值。

3. 最终，dp[N][C]就是能够获得的最大价值。

接下来，我们可以通过可视化的方式来展示动态规划的过程。具体实现如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<sstream>
using namespace std;

const int N=1e3+10;
int n,m,w[N],v[N],dp[N][N];
bool st[N][N];//用于记录每个状态是否被更新过

void print()
{
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(st[i][j]) printf("√ ");
            else printf("× ");
        }
        printf("\n");
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=w[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
            if(dp[i][j]!=dp[i-1][j]) st[i][j]=true;//如果更新了状态，就记录下来
        }

    printf("最大价值为%d\n",dp[n][m]);
    print();//输出每个状态是否被更新过
    return 0;
}

在程序运行过程中，我们记录下每个状态是否被更新过，然后输出该二维数组。如果某个状态被更新过，就用“√”表示；否则，用“×”表示。这样，我们就可以清楚地看到动态规划的过程。