Trong bài toán cái ba lô 0-1 (0-1 Knapsack), một tập hợp vật phẩm được cho, mỗi vật phẩm có một trọng lượng và một giá trị. Chúng ta cần xác định số lượng mỗi vật phẩm để đưa vào tập hợp sao cho tổng trọng lượng nhỏ hơn hoặc bằng giới hạn cho trước và tổng giá trị càng lớn càng tốt.
Đầu vào
Giá trị = [10, 20, 30, 40, 60, 70] Trọng lượng = [1, 2, 3, 6, 7, 4] int w = 7
Đầu ra
Giá trị ba lô là: 100
Thuật toán
Bắt đầu Đầu vào: tập vật phẩm mỗi cái có trọng lượng và giá trị Đặt dung lượng ba lô Số vật phẩm = sizeof(values) / sizeof(values[0]) Knapsack(Giá trị (lưu trong mảng v), Trọng lượng (lưu trong mảng w), Số vật phẩm khác nhau (n), Dung lượng ba lô W) Nếu (w < 0) Trả về Nếu không còn vật phẩm hoặc dung lượng bằng 0 Trả về 0 Bao gồm vật phẩm hiện tại n trong ba lô (v[n]) và đệ quy cho các vật phẩm còn lại (n - 1) với dung lượng giảm (W - w[n]) Loại trừ vật phẩm hiện tại n khỏi ba lô và đệ quy cho các vật phẩm còn lại (n - 1) Trả về giá trị lớn nhất thu được bằng cách bao gồm hoặc loại trừ vật phẩm hiện tại Kết thúc
Mã ví dụ
#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 << "Giá trị ba lô là: " << knapSack(v, w, n - 1, W);
return 0;
}Kết quả
Giá trị ba lô là: 100