C++动态规划实现0-1背包问题求解 |21xrx.com

C++动态规划实现0-1背包问题求解

2023-07-02 05:52:00 深夜i -- --

C++ 动态规划 0-1背包问题实现求解

0-1背包问题是在特定的背包容量下，在一组物品中选择一定数量的物品，使得选中的物品总重量不超过容量，而价值最高。这是一个NP完全问题，可以用动态规划算法来解决。在本文中，我们将介绍如何使用C++语言实现0-1背包问题的动态规划算法。

首先，需要定义一个二维数组来保存问题的最优解。对于N个物品和M的背包容量，数组dp[N+1][M+1]的值表示在前n个物品中选出重量不超过m的物品所获得的最大价值。

接下来，使用循环嵌套遍历每一件物品和每一个容量，计算每个选项的价值。对于第i个物品，如果它的重量小于当前的背包容量，则可以选择将该物品放入背包中，获得价值vi，并计算使用第i个物品所得到的最优价值。这可以用以下公式来表示：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

其中，w表示第i个物品的重量，v表示其价值。如果第i个物品的重量大于当前背包容量，则不能将其放入背包中，所以此时的最优解与前i-1个物品的最优解相同。这可以用以下公式来表示：

dp[i][j] = dp[i-1][j]

最后，在计算完整个数组后，dp[N][M]的值就是所求的最大价值。

下面是完整的C++代码实现：


#include<iostream>
#include<cstring>
using namespace std;
int max(int a, int b) { return (a > b) ? a : b; }
int knapSack(int W, int wt[], int val[], int n)
{
  int i, w;
  int **dp = new int*[n + 1];
  for(i = 0; i <= n; i++)
    dp[i] = new int[W + 1];
  for (i = 0; i <= n; i++)
  {
    for (w = 0; w <= W; w++)
    {
      if (i == 0 || w == 0)
        dp[i][w] = 0;
      else if (wt[i - 1] <= w)
        dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]],dp[i - 1][w]);
      else
        dp[i][w] = dp[i - 1][w];
    }
  }
  int res = dp[n][W];
  for(i = 0; i <= n; i++)
    delete[] dp[i];
  delete[] dp;
  
  return res;
}
int main()
{
  int val[] = 10;
  int wt[] = 1;
  int W = 5;
  int n = sizeof(val) / sizeof(val[0]);
  cout << knapSack(W, wt, val, n);
  return 0;
}

运行上述代码将输出：60，表示使用前三个物品可以获得60的最大价值，可以用以下物品组合：

30，总重量为5

总之，本文介绍了如何使用C++语言实现0-1背包问题的动态规划算法。通过定义二维数组，循环遍历每个物品和容量，并使用决策公式计算最优解，可以求解该NP完全问题。

上一篇: idea打包java可执行jar包

下一篇: C++中的循环指令使用

评论区

()

相似文章