Chương trình C ++ để giải quyết vấn đề 0-1 Knapsack

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.

Đầu vào

Value = [10, 20, 30, 40, 60, 70]
Weight=[1, 2, 3, 6, 7, 4]
int w=7

Đầu ra

knapsack value is: 100

Thuật toán

Begin
   Input: set of items each with a weight and a value
   Set knapsack capacity
   Number of items=sizeof(values) / sizeof(values[0])
   Knapsack(Values (stored in array v), Weights (stored in array w), Number of
   distinct items (n), Knapsack capacity W)
   If (w < 0)
      Return
   If no items left or capacity becomes 0
      Return 0
   Include current item n in knapSack (v[n]) and recurs for
   remaining items (n - 1) with decreased capacity (W - w[n])
   Exclude current item n from knapSack and recurs for
   remaining items (n - 1)
   Return maximum value we get by including or excluding current item
End

Mã mẫu

#include <iostream>
#include <climits>
using namespace std;
int knapSack(int v[], int w[], int n, int W) {
   if (W < 0)
      return INT_MIN;
   if (n < 0 || W == 0)
      return 0;
   int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
   int ex = knapSack(v, w, n - 1, W);
   return max (in, ex);
}
int main() {
   int v[] = { 10, 20, 30, 40, 60, 70 };
   int w[] = { 1, 2, 3, 6, 7, 4 };
   int W = 7;
   int n = sizeof(v) / sizeof(v[0]);
   cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
   return 0;
}

Đầu ra

Knapsack value is 100