使用动态规划解决背包问题的 C++ 程序

这是一个使用动态规划解决 0-1 背包问题的 C++ 程序。在 0-1 背包问题中，给定一组物品，每种物品都具有重量和价值。我们需要确定每件物品包含在集合中的数量，以便总重量小于或等于给定的限制，并且总价值尽可能大。

算法

Begin
Input set of items each with a weight and a value
Set knapsack capacity
Create a function that returns maximum of two integers.
Create a function which returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int w[], int v[], int n)
int i, wt;
int K[n + 1][W + 1]
for i = 0 to n
for wt = 0 to W
if (i == 0 or wt == 0)
   Do K[i][wt] = 0
else if (w[i - 1] <= wt)
   Compute: K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i -1][wt])
else
   K[i][wt] = K[i - 1][wt]
   return K[n][W]
   Call the function and print.
End

示例代码

#include <iostream>
using namespace std;
int max(int x, int y) {
   return (x > y) ? x : y;
}
int knapSack(int W, int w[], int v[], int n) {
   int i, wt;
   int K[n + 1][W + 1];
   for (i = 0; i <= n; i++) {
      for (wt = 0; wt <= W; wt++) {
         if (i == 0 || wt == 0)
         K[i][wt] = 0;
         else if (w[i - 1] <= wt)
            K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);
         else
        K[i][wt] = K[i - 1][wt];
      }
   }
   return K[n][W];
}
int main() {
   cout << "Enter the number of items in a Knapsack:";
   int n, W;
   cin >> n;
   int v[n], w[n];
   for (int i = 0; i < n; i++) {
      cout << "Enter value and weight for item " << i << ":";
      cin >> v[i];
      cin >> w[i];
   }
   cout << "Enter the capacity of knapsack";
   cin >> W;
   cout << knapSack(W, w, v, n);
   return 0;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

Enter the number of items in a Knapsack:4
Enter value and weight for item 0:10
50
Enter value and weight for item 1:20
60
Enter value and weight for item 2:30
70
Enter value and weight for item 3:40
90
Enter the capacity of knapsack100
40

更新于: 2019-07-30

14K+ 浏览

开启你的 职业生涯

完成课程即可获得证书

开始
广告