C++动态规划小偷问题：实现输入输出的代码 |21xrx.com

C++动态规划小偷问题：实现输入输出的代码

2023-07-02 19:11:55 深夜i -- --

C++ 动态规划小偷问题输入输出

动态规划算法是一种求解最优化问题的有效方法。在小偷问题中，我们需要考虑最优的偷窃策略，使得盗窃的价值最大化，同时不被发现。这个问题可以使用动态规划来解决。

下面是一个使用C++实现动态规划求解小偷问题的代码。它包含了输入和输出的功能，可以让你更好地理解这个问题。


#include <iostream>
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 K[n + 1][W + 1];
  for (i = 0; i <= n; i++) {
    for (w = 0; w <= W; w++) {
      if (i == 0 || w == 0)
        K[i][w] = 0;
      else if (wt[i - 1] <= w)
        K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
      else
        K[i][w] = K[i - 1][w];
    }
  }
  return K[n][W];
}
int main() {
  int n, W;
  cout << "Enter the number of items: ";
  cin >> n;
  int val[n], wt[n];
  for (int i = 0; i < n; i++) {
    cout << "Enter the value and weight of item " << i + 1 << ": ";
    cin >> val[i] >> wt[i];
  }
  cout << "Enter the capacity of knapsack: ";
  cin >> W;
  cout << "The maximum value that can be put in a knapsack of capacity " << W << " is " << knapsack(W, wt, val, n);
  return 0;
}

这段代码中，我们首先定义了一个max函数，用于计算两个值中的最大值。然后我们定义了一个knapsack函数，用于实现动态规划算法，返回能够放入背包的最大价值。

在main函数中，我们可以输入背包的容量W、物品的数量n、物品的价值val和重量wt。最后输出能够放入背包的最大价值。

总之，以上C++代码通过输入和输出演示了动态规划小偷问题。这一问题在生产和实际生活中具有重要意义，值得深入研究和探讨。

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

下一篇: C++中如何表示绝对值

评论区

()

相似文章