Chương trình C ++ để giải quyết vấn đề Knapsack bằng lập trình động

Đây là một chương trình C ++ để giải quyết vấn đề 0-1 knapsack bằng cách sử dụng lập trình động. Trong bài toán ba lô 0-1, một tập hợp các mục được đưa ra, mỗi mục có trọng lượng và giá trị. Chúng tôi cần xác định số lượng của từng món để đưa vào bộ sưu tập sao cho tổng trọng lượng nhỏ hơn hoặc bằng giới hạn đã cho và tổng giá trị càng lớn càng tốt.

Thuật toán

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

Mã mẫu

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

Đầu ra

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