SPOJ.COM - Thuật toán bài LKS - Large Knapsack

Posted on October 29th, 2016

Đề 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

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ì mình 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 mình không thể sử dụng một mảng 2 chiều NxK được. Tuy nhiên, nếu 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 bạn sẽ thấy rõ hơn ở dưới). Nên mình 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, mình lại hoán đổi vai trò của hai hàng cho nhau. Cứ như vậy, mình sẽ tính được giá trị của hàng thứ N.

Lời giải

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 mình 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 mình 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 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.
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé: