Đây là chương trình C++ giải bài toán Cái ba lô 0-1 (0-1 Knapsack) bằng quy hoạch động. Trong bài toán 0-1 Knapsack, một tập hợp các vật phẩm được cho, mỗi vật phẩm có trọng lượng và 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ị lớn nhất có thể.
Thuật toán
Bắt đầu
Nhập tập vật phẩm mỗi vật có trọng lượng và giá trị.
Đặt dung lượng ba lô.
Tạo hàm trả về lớn hơn của hai số nguyên.
Tạo hàm trả về giá trị lớn nhất có thể bỏ vào ba lô dung lượng W:
int knapSack(int W, int w[], int v[], int n)
int i, wt;
int K[n + 1][W + 1]
với i = 0 đến n
với wt = 0 đến W
nếu (i == 0 hoặc wt == 0) K[i][wt] = 0
khác nếu (w[i - 1] <= wt)
K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt])
khác K[i][wt] = K[i - 1][wt]
trả về K[n][W]
Gọi hàm và in kết quả.
Kết thúc
Mã ví dụ
#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 << "Nhập số vật phẩm trong ba lô: ";
int n, W;
cin >> n;
int v[n], w[n];
for (int i = 0; i < n; i++) {
cout << "Nhập giá trị và trọng lượng cho vật phẩm " << i << ": ";
cin >> v[i];
cin >> w[i];
}
cout << "Nhập dung lượng ba lô: ";
cin >> W;
cout << knapSack(W, w, v, n);
return 0;
}
Kết quả
Nhập số vật phẩm trong ba lô: 4 Nhập giá trị và trọng lượng cho vật phẩm 0: 10 50 Nhập giá trị và trọng lượng cho vật phẩm 1: 20 60 Nhập giá trị và trọng lượng cho vật phẩm 2: 30 70 Nhập giá trị và trọng lượng cho vật phẩm 3: 40 90 Nhập dung lượng ba lô: 100 40