SPOJ.COM – Thuật toán bài LKS - Large Knapsack
Đề bài:
Bài toán knapsack hay rucksack là một bài toán trong combinatorial optimization: Cho một tập gồm những phần tử. mỗi phần tử bao gồm trọng lượng và giá trị. Xác định số lượng mỗi phần tử được chọn sao cho tổng trọng lượng nhỏ hơn hoặc bằng với giới hạn cho trước và tổng giá trị là lớn nhất có thể.
Đầu vào:
Dòng đầu tiên bao gồm 2 số nguyên K và N, trong đó K là kích thước giới hạn của cái túi (knapsack) và N là số lượng phần tử. N dòng tiếp theo trong đó dòng thứ i là phần tử thứ i với giá trị vi và trọng lượng wi.
Đầu ra:
In ra số nguyên duy nhất, là giá trị lớn nhất có thể của chiếc túi. (Tất cả các phép toán đảm bảo trong phạm vi của số nguyên có dấu 32 bit)
Ví dụ:
Đầu vào:
10 3
7 3
8 8
4 6
Đầu ra:
11
Giới hạn:
K <= 2000000
N <= 500
Vi <= 10^7
Wi <= 10^7
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/LKS/
Phân tích:
-
Đây là bái toán Knapsack 0/1 cơ bản. Nghĩa là mỗi đồ vật sẽ có thể được chọn hay không được chọn. Và nếu được chọn thì không giới hạn số lần chọn. Thuật toán được sử dụng ở đây là thuật toán quy hoạch động Dynamic Programming
-
Bình thường thì tôi sẽ sử dụng một mảng hai chiều kích thước NxK, là
MaxCost[N][K]. Trong đó,MaxCost[i][j]là giá trị lớn nhất thu được với việc chọn đồ vật từ 1 đến i và trọng lượng không vượt quá j. -
Nhưng do số lượng đầu vào khá lớn nên tôi không thể sử dụng một mảng 2 chiều NxK được. Tuy nhiên, nếu các bạn để ý rằng giá trị tại hàng thứ i chỉ phụ thuộc vào hàng trước đó i - 1 (thuật toán các bạn sẽ thấy rõ hơn ở dưới). Nên tôi chỉ cần một mảng 2 chiều 2xK, trong đó một hàng dùng để lưu giá trị hàng thứ i - 1 và một hàng lưu giá trị hàng i. Sau khi tính được hàng i, tôi lại hoán đổi vai trò của hai hàng cho nhau. Cứ như vậy, tôi sẽ tính được giá trị của hàng thứ N.
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/ C++:
| #include <iostream> | |
| using namespace std; | |
| const int MAX_N = 505; | |
| const int MAX_K = 2000005; | |
| int K, N; | |
| int Value[MAX_N], Weight[MAX_N]; | |
| int MaxCost[2][MAX_K]; | |
| // MAX[1][j] là giá trị lớn nhất thu được | |
| // với việc chọn từ đồ vật từ 1 đến i và | |
| // khối lượng không vượt quá j | |
| // MAX[0][j] là giá trị cũ trước đó. | |
| // Và ngược lại | |
| int Max(int a, int b) | |
| { | |
| if(a > b) return a; | |
| return b; | |
| } | |
| int main() | |
| { | |
| int T, test_case; | |
| ios::sync_with_stdio(false); | |
| //freopen("input.txt", "r", stdin); | |
| cin >> K >> N; | |
| for(int i = 1; i <= N; i++) | |
| cin >> Value[i] >> Weight[i]; | |
| // Trường hợp cơ sở | |
| for(int j = 0; j <= K; j++) | |
| MaxCost[0][j] = 0; | |
| for(int i = 0; i < 2; i++) | |
| MaxCost[i][0] = 0; | |
| int before = 0, current = 1; | |
| for(int i = 1; i <= N; i++) | |
| { | |
| for(int j = 1; j <= K; j++) | |
| { | |
| // Không chọn vật i | |
| MaxCost[current][j] = MaxCost[before][j]; | |
| // Chọn vật i | |
| if(Weight[i] <= j) MaxCost[current][j] = | |
| Max(MaxCost[current][j], MaxCost[before][j - Weight[i]] + Value[i]); | |
| } | |
| // Đổi current và before cho nhau. | |
| current = 1 - current; | |
| before = 1 - before; | |
| } | |
| // N chẵn thì kết quả là MaxCost[0][K] | |
| // N lẻ thì kết quả là MaxCost[1][K] | |
| cout << MaxCost[N % 2][K] << endl; | |
| return 0;//Your program should return 0 on normal termination. | |
| } |
Code by Phạm Văn Lâm.