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;
}

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