SPOJ.COM - Thuật toán bài ABA12C - Buying Apples

Đề bài:

Mạnh đã đến siêu thị để mua chính xác "k" Kg táo cho "n" người bạn của anh ta. Tuy nhiên siêu thị này rất kì lạ. Giá của các sản phẩm rất là khác nhau. Do đó, Mạnh đã đi đến khu vực bán táo để hỏi về giá của chúng. Người bán hàng đưa cho anh ta một cái bảng giá. Và Mạnh nhận thấy rằng giá của táo không được tính dựa trên 1 Kg. Táo được đóng gói trong bao bì, mỗi cái chứa 'x' Kg táo, x > 0 và 'x' là số nguyên. Một gói 'x' Kg táo có giá là 'y' VNĐ. Vì vậy có một tấm bảng được đặt trên bàn với số 'y' là giá của của một gói 'x' Kg táo. Nếu 'y' là -1 thì nó có nghĩa là gói đó sẽ không được bán. Với những thông tin như vậy, Mạnh quyết định mua tối đa 'n' gói cho 'n' người bạn của anh ấy. Nói cách khác là Mạnh không được phép mua nhiều hơn 'n' gói táo.

Mạnh rất quý bạn của anh ấy nên không muốn làm thất vọng họ. Bây giờ, anh ấy sẽ nói cho bạn biết về số lượng những người bạn. Và bạn phải nói cho anh ấy biết về số lượng tiền tối thiểu mà Mạnh phải bỏ ra.

Đầu vào

Dòng đầu tiên là số lượng test cases, C. Mỗi test case sẽ gồm 2 dòng. Dòng đầu tiên chứa số N và K, lần lượt là số lượng bạn của anh ấy và lượng táo (Kg) mà Mạnh muốn mua. Dòng thứ hai bao gồm K số nguyên phân biệt với nhau bởi dấu cách. Trong đó, số nguyên thứ i là giá của gói 'i' Kg. Và giá trị -1 có nghĩa là gói tương ứng sẽ không được bán. (i được tính từ 1)

Ràng buộc:

0 < N <= 100 
0 < K <= 100 
0 < Giá tiền <= 1000

Đầu ra

Đầu ra cho mỗi test case là một dòng chứa số lượng tiền mà Mạnh phải bỏ ra. In ra -1 nếu như Mạnh không thể làm hài lòng bạn anh ấy.

Ví dụ

Đầu vào:

2 
3 5 
-1 -1 4 5 -1 
5 5 
1 2 3 4 5 

Đầu ra:

-1 
5 

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/ABA12C/

Giải thích:

1. Có N = 3 người bạn, K = 5 Kg táo cần mua. Tiếp theo là giá của 5 gói (1, 2, 3, 4, 5) Kg. Tuy nhiên gói 1, 2 và 5 Kg không bán. Do đó chỉ còn gói 3 và 4 Kg. Nên Mạnh không thể mua chính xác 5 Kg táo. Vì vậy, anh ấy không thể làm hài lòng những người bạn.

2. Có N = 5 người bạn, K = 5 Kg táo cần mua. Giá của các gói 1, 2, 3, 4, 5 Kg tương ứng là 1, 2, 3, 4, 5. Mạnh có thể mua 5 gói 1 Kg. Vì vậy số tiền nhỏ nhất mà Mạnh cần bỏ ra là 5.

Phân tích

Đầu vào N, K có giá trị lớn nhất là 100. Nếu bạn giải quyết bài toán sử dụng phương pháp vét cạn. Thì ở đây, mỗi gói sẽ có hai khả năng là được chọn hoặc không.

=> Độ phức tạp của thuật toán trong trường hợp xấu nhất là 2^100 (thực tế độ phức tạp tính ra là 1000000000 thì thời gian chạy sẽ xấp xỉ 1 giây). Do đó, dùng vét cạn sẽ bị time limit.

Với những bài toán dạng này, ta sẽ sử dụng phương pháp quy hoạch động.

Với chú ý ở đây là: MinMoney[i] = Min{MinMoney[i], MinMoney[j] + Price[i - j]}

Trong đó:

• MinMoney[i], MinMoney[j] là số tiền nhỏ nhất để mua đúng i , j kg

• Price[i - j] là giá của gói 'i - j' kg.

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 = 105;

int N;                  // Số lượng bạn
int K;                  // Số lượng Kg táo cần mua
int Price[MAX];         // Lưu giá của các gói, Price[i] ứng với giá của gói thứ i
int MinMoney[MAX][MAX]; // MinMoney[i][j]: Số tiền nhỏ nhất cần bỏ ra để mua i Kg táo,
                        // và số gói không quá j
int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);

	int Testcase = 0;
	cin >> Testcase;
	for(int tc = 0; tc < Testcase; tc++)
	{
		cin >> N >> K;
		for(int i = 1; i <= K; i++)
		{
			cin >> Price[i];

			// Khởi tạo số tiền nhỏ nhất cần bỏ ra để mua chính xác i Kg táo,
			// chính là số tiền cần bỏ ra để mua 1 gói 'i' Kg táo.
			for(int j = 1; j <= N; j++)
				MinMoney[i][j] = Price[i];
		}

		// Cập nhật lại mảng MinMoney[] sử dụng quy hoạch động
		for(int i = 2; i <= K; i++)
			for(int x = 2; x <= N; x++)
				for(int j = 1; j < i; j++)
				{
					if(MinMoney[j][x - 1] < 0 || Price[i - j] < 0) continue;

					// Khi chưa có giá trị MinMoney[i], thì lượng tiền nhỏ nhất
					// chính là lượng tiền nhỏ nhất khi đã mua 'j' Kg
					// và mua thêm 'i-j' Kg
					int temp = MinMoney[j][x - 1] + Price[i - j];
					if(MinMoney[i][x] < 0 || temp < MinMoney[i][x])
						MinMoney[i][x] = temp;
				}
		cout << MinMoney[K][N] << endl;
	}
	return 0;
}

Code Python:

num_tc = int(raw_input())
for tc in xrange(0, num_tc):
    # Nhap dau vao
    N, K = map(int, raw_input().split())

    price = [0] * (K + 1)
    price[1:K+1] = map(int, raw_input().split())

    # Khoi tao so tien nho nhat de mua i kg tao
    # la so tien de mua 1 goi i Kg tao

    min_price = [([0] * (N + 1)) for row in xrange(K + 1)]

    for i in xrange(1, K + 1):
        for j in xrange(1, N + 1):
            min_price[i][j] = price[i]

    for i in xrange(2, K + 1):
        for x in xrange(2, N + 1):
            for j in xrange(1, i):
                if min_price[j][x - 1] < 0 or price[i - j] < 0 :
                    continue

                temp = min_price[j][x - 1] + price[i - j]

                if min_price[i][x] < 0 or temp < min_price[i][x]:
                    min_price[i][x] = temp

    print min_price[K][N]