C++实现背包问题的代码 |21xrx.com

C++实现背包问题的代码

2023-07-09 18:31:54 深夜i -- --

C++ 背包问题代码实现

背包问题是计算机科学中经典的问题之一，它的应用范围非常广泛，如商业货物的装载、资源分配和编程语言的词法分析等。C++是一种流行的编程语言，有着广泛的应用，下面是C++实现背包问题的代码。

背包问题的定义是：给定一组有价值和重量的物品，以及一个容量为W的背包。要求选择出若干物品放入背包中，使得它们的总重量不超过W，且价值最大。

以下是用C++实现背包问题的代码：


#include <bits/stdc++.h>
using namespace std;
int knapsack(int W, int wt[], int val[], int n)
{
  int K[n + 1][W + 1];
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
      if (i == 0 || j == 0) {
        K[i][j] = 0;
      }
      else if (wt[i - 1] <= j) {
        K[i][j] = max(val[i - 1] + K[i - 1][j - wt[i - 1]], K[i - 1][j]);
      }
      else {
        K[i][j] = K[i - 1][j];
      }
    }
  }
  return K[n][W];
}
int main()
{
  int val[] = 100;
  int wt[] = 10;
  int W = 50;
  int n = sizeof(val) / sizeof(val[0]);
  cout << knapsack(W, wt, val, n) << endl;
  return 0;
}

该代码中使用了动态规划的思想，通过二维数组K[i][j]来存储前i个物品在重量不超过j的情况下的最大价值。在每个物品的扫描中，当当前物品的重量小于等于背包容量时，根据是否选择该物品进行分情况计算。如果选择该物品，那么最大价值就是该物品价值加上前i-1个物品在重量为j-当前物品重量的情况下的最大价值；反之，最大价值就是前i-1个物品在重量为j的情况下的最大价值。最后返回K[n][W]即可得到最大价值。

在主函数中，我们使用了一个简单的例子进行验证，有三个物品，重量为10、20、30，价值分别为60、100、120，容量为50的背包。最终输出结果为220，验证了算法的正确性。

以上就是C++实现背包问题的代码，C++的运行速度快且稳定，非常适合解决算法问题。这个代码可以帮助初学者快速入门并理解动态规划的思想，也可以为工程师提供一个高效的解决方案。

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

下一篇: C++输出空格间隔的实现方法

评论区

()

相似文章