Bài 17.4. Bài toán cái túi phân số và ứng dụng

Bài 17.4: Bài toán cái túi phân số và ứng dụng

Chào mừng các bạn quay trở lại với series blog của chúng ta về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau tìm hiểu một bài toán tối ưu kinh điển nhưng lại có lời giải khá "ngọt ngào" và đơn giản: Bài toán cái túi phân số (Fractional Knapsack Problem).

Đây là một phiên bản đặc biệt của Bài toán cái túi tổng quát, và nó cho chúng ta cái nhìn sâu sắc về sức mạnh (và giới hạn) của các thuật toán tham lam (Greedy Algorithms).

Bài toán cái túi phân số là gì?

Hãy tưởng tượng bạn đang chuẩn bị cho một chuyến đi phiêu lưu và chỉ có một chiếc túi (cái túi của bạn!) với một dung lượng tối đa cho trước (ví dụ: sức chứa về trọng lượng). Bạn đang đứng trước một đống các món đồ quý giá, mỗi món có một trọng lượng nhất định và một giá trị tương ứng.

Mục tiêu của bạn: Chọn các món đồ bỏ vào túi sao cho tổng giá trị thu được là lớn nhất.
Ràng buộc: Tổng trọng lượng của các món đồ trong túi không được vượt quá dung lượng tối đa của túi.

Điểm đặc biệt và làm nên sự khác biệt của Bài toán cái túi phân số so với phiên bản 0/1 (Bài toán cái túi 0/1) là: bạn được phép lấy một phần của một món đồ. Tức là, nếu bạn thấy chỉ còn đủ chỗ cho nửa gói vàng, bạn hoàn toàn có thể cắt gói vàng đó và chỉ lấy nửa gói, nhận về nửa giá trị và nửa trọng lượng.

Tóm lại: Cho $n$ món đồ, mỗi món có trọng lượng $w_i$ và giá trị $v_i$. Cho một cái túi có sức chứa tối đa là $W$. Cần chọn một lượng $x_i$ của mỗi món đồ $i$ ($0 \le x_i \le 1$, trong đó $x_i=1$ nghĩa là lấy toàn bộ, $x_i=0.5$ nghĩa là lấy một nửa, ...) sao cho $\sum_{i=1}^n x_i \cdot w_i \le W$ và tổng giá trị $\sum_{i=1}^n x_i \cdot v_i$ là lớn nhất.

Tại sao thuật toán tham lam lại hiệu quả ở đây?

Ở Bài toán cái túi 0/1, việc sử dụng thuật toán tham lam (chọn theo giá trị, hoặc theo trọng lượng, hoặc theo tỉ lệ giá trị/trọng lượng) không đảm bảo cho ta kết quả tối ưu. Lý do là việc chọn (hoặc không chọn) một món đồ nguyên vẹn có thể ảnh hưởng lớn đến khả năng chứa các món đồ khác sau này theo những cách phức tạp.

Tuy nhiên, với Bài toán cái túi phân số, khả năng lấy một phần của món đồ loại bỏ sự phức tạp này. Nếu bạn còn một khoảng trống nhỏ trong túi, bạn luôn có thể lấp đầy khoảng trống đó bằng một phần của món đồ hiệu quả nhất còn lại (tức là món đồ có giá trị trên mỗi đơn vị trọng lượng cao nhất) để tối đa hóa giá trị thu thêm trên khoảng trống đó.

Điều này dẫn đến một chiến lược tham lam rất trực quan:

Chiến lược tham lam: Ưu tiên chọn các món đồ có tỉ lệ giá trị trên mỗi đơn vị trọng lượng ($v_i / w_i$) cao nhất.

Lý do rất đơn giản: Để lấp đầy chiếc túi, bạn muốn mỗi kilogram (hoặc đơn vị trọng lượng bất kỳ) mà bạn thêm vào mang lại cho bạn nhiều giá trị nhất có thể. Món đồ nào có tỉ lệ $v_i / w_i$ càng cao thì càng "đáng giá" trên mỗi đơn vị trọng lượng.

Thuật toán giải Bài toán cái túi phân số

Dựa trên chiến lược tham lam vừa nêu, chúng ta có các bước sau để giải bài toán:

Tính toán tỉ lệ giá trị/trọng lượng: Đối với mỗi món đồ $i$, tính tỉ lệ $r_i = v_i / w_i$.
Sắp xếp: Sắp xếp các món đồ theo tỉ lệ $r_i$ này theo thứ tự giảm dần.
Điền vào túi: Duyệt qua các món đồ đã được sắp xếp từ món có tỉ lệ cao nhất:
- Nếu chiếc túi còn đủ chỗ để chứa toàn bộ món đồ hiện tại ($w_i \le$ dung lượng còn lại), hãy lấy toàn bộ nó. Cộng giá trị $v_i$ vào tổng giá trị và giảm dung lượng còn lại của túi đi $w_i$.
- Nếu chiếc túi không còn đủ chỗ để chứa toàn bộ món đồ, hãy tính xem có thể lấy được bao nhiêu phần của món đồ đó. Lượng phần trăm có thể lấy là (dung lượng còn lại) / $w_i$. Lấy phần này của món đồ, cộng giá trị tương ứng ((dung lượng còn lại / $w_i$) * $v_i$) vào tổng giá trị, và chiếc túi sẽ đầy (dung lượng còn lại về 0). Kết thúc quá trình.

Bước 3 đảm bảo rằng chúng ta luôn lấp đầy dung lượng còn lại của túi bằng món đồ hiệu quả nhất có thể vào thời điểm đó. Vì được phép lấy phân số, việc này luôn mang lại kết quả tối ưu.

Minh họa bằng C++

Chúng ta cần một cấu trúc để biểu diễn các món đồ và một hàm so sánh để sắp xếp chúng theo tỉ lệ giá trị/trọng lượng.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip> // Dùng để định dạng output số thực

// Cấu trúc biểu diễn một món đồ
struct Item {
    int weight; // Trọng lượng
    int value;  // Giá trị
    double ratio; // Tỉ lệ giá trị/trọng lượng (value / weight)

    // Constructor
    Item(int w, int v) : weight(w), value(v) {
        if (w > 0) {
            ratio = static_cast<double>(v) / w;
        } else {
            ratio = 0; // Hoặc một giá trị phù hợp khác nếu trọng lượng là 0
        }
    }
};

// Hàm so sánh cho std::sort
// Sắp xếp các món đồ theo tỉ lệ ratio giảm dần
bool compareItems(const Item& a, const Item& b) {
    return a.ratio > b.ratio;
}

// Hàm giải bài toán cái túi phân số
double fractionalKnapsack(int capacity, std::vector<Item>& items) {
    // Bước 1 & 2: Tính ratio và sắp xếp
    // Ratio đã được tính trong constructor. Chỉ cần sắp xếp.
    std::sort(items.begin(), items.end(), compareItems);

    double totalValue = 0.0; // Tổng giá trị thu được
    int currentWeight = 0; // Trọng lượng hiện tại trong túi

    std::cout << "--- Qua trinh dien tui ---" << std::endl;

    // Bước 3: Điền vào túi theo thứ tự đã sắp xếp
    for (const auto& item : items) {
        // Nếu lấy toàn bộ món đồ này không vượt quá dung lượng còn lại
        if (currentWeight + item.weight <= capacity) {
            currentWeight += item.weight;
            totalValue += item.value;
            std::cout << "Lay toan bo mon do nang " << item.weight << "kg, tri gia " << item.value << "$ (ratio: " << std::fixed << std::setprecision(2) << item.ratio << ")."
                      << " Tong trong luong: " << currentWeight << "kg, Tong gia tri: " << totalValue << "$" << std::endl;
        } else {
            // Nếu không thể lấy toàn bộ, tính phần trăm có thể lấy
            int remainingCapacity = capacity - currentWeight;
            double fraction = static_cast<double>(remainingCapacity) / item.weight;

            totalValue += fraction * item.value;
            currentWeight += remainingCapacity; // Túi đầy

            std::cout << "Chi lay mot phan (" << std::fixed << std::setprecision(2) << fraction * 100 << "%) mon do nang " << item.weight << "kg, tri gia " << item.value << "$ (ratio: " << std::fixed << std::setprecision(2) << item.ratio << ")."
                      << " Tuong ung " << std::fixed << std::setprecision(2) << fraction * item.weight << "kg, gia tri " << std::fixed << std::setprecision(2) << fraction * item.value << "$."
                      << " Tong trong luong: " << currentWeight << "kg, Tong gia tri: " << totalValue << "$" << std::endl;

            break; // Túi đã đầy, không cần xem xét các món đồ còn lại
        }
    }
    std::cout << "-------------------------" << std::endl;

    return totalValue;
}

int main() {
    // Ví dụ 1
    std::cout << "--- Vi du 1 ---" << std::endl;
    int capacity1 = 50;
    std::vector<Item> items1;
    items1.push_back(Item(10, 60));
    items1.push_back(Item(20, 100));
    items1.push_back(Item(30, 120));

    double max_value1 = fractionalKnapsack(capacity1, items1);
    std::cout << "Dung luong tui: " << capacity1 << "kg" << std::endl;
    std::cout << "Tong gia tri toi da thu duoc: " << std::fixed << std::setprecision(2) << max_value1 << "$" << std::endl;
    std::cout << std::endl;


    // Ví dụ 2
    std::cout << "--- Vi du 2 ---" << std::endl;
    int capacity2 = 20;
    std::vector<Item> items2;
    items2.push_back(Item(5, 30));
    items2.push_back(Item(10, 20));
    items2.push_back(Item(15, 45));
    items2.push_back(Item(2, 15));


    double max_value2 = fractionalKnapsack(capacity2, items2);
    std::cout << "Dung luong tui: " << capacity2 << "kg" << std::endl;
    std::cout << "Tong gia tri toi da thu duoc: " << std::fixed << std::setprecision(2) << max_value2 << "$" << std::endl;
    std::cout << std::endl;

    // Ví dụ 3 (Trường hợp không lấy hết dung lượng)
    std::cout << "--- Vi du 3 ---" << std::endl;
    int capacity3 = 15;
    std::vector<Item> items3;
    items3.push_back(Item(10, 100));
    items3.push_back(Item(5, 50));
    items3.push_back(Item(20, 120)); // Ratio 6, 10, 6
    items3.push_back(Item(3, 40));  // Ratio 13.33

    double max_value3 = fractionalKnapsack(capacity3, items3);
    std::cout << "Dung luong tui: " << capacity3 << "kg" << std::endl;
    std::cout << "Tong gia tri toi da thu duoc: " << std::fixed << std::setprecision(2) << max_value3 << "$" << std::endl;
    std::cout << std::endl;


    return 0;
}

Giải thích mã C++

struct Item: Chúng ta định nghĩa một cấu trúc để lưu trữ thông tin về mỗi món đồ: weight (trọng lượng), value (giá trị) và ratio (tỉ lệ giá trị/trọng lượng). ratio được tính ngay trong constructor khi một đối tượng Item được tạo ra, giúp đơn giản hóa logic sau này.
compareItems(const Item& a, const Item& b): Đây là một hàm so sánh tùy chỉnh được sử dụng bởi std::sort. Nó trả về true nếu món đồ a có tỉ lệ ratio lớn hơn món đồ b, đảm bảo std::sort sắp xếp danh sách các món đồ theo thứ tự tỉ lệ giảm dần.
fractionalKnapsack(int capacity, std::vector<Item>& items):
- Hàm này nhận vào dung lượng tối đa của túi (capacity) và một vector chứa các Item.
- std::sort(items.begin(), items.end(), compareItems); thực hiện việc sắp xếp các món đồ theo tỉ lệ ratio giảm dần. Đây là bước quan trọng nhất của thuật toán tham lam.
- Chúng ta khởi tạo totalValue (tổng giá trị thu được) và currentWeight (trọng lượng hiện tại trong túi) ban đầu là 0.
- Vòng lặp for (const auto& item : items) duyệt qua từng món đồ đã được sắp xếp, bắt đầu từ món có tỉ lệ cao nhất.
- Bên trong vòng lặp:
  - if (currentWeight + item.weight <= capacity): Kiểm tra xem món đồ hiện tại có thể được bỏ toàn bộ vào túi mà không vượt quá dung lượng không. Nếu có, chúng ta thêm toàn bộ trọng lượng và giá trị của nó vào tổng cộng, cập nhật currentWeight và totalValue.
  - else: Nếu không đủ chỗ cho toàn bộ món đồ, chúng ta tính toán phần trăm (fraction) của món đồ có thể vừa với dung lượng còn lại (remainingCapacity). Chúng ta chỉ lấy phần này của món đồ, cộng giá trị tương ứng (fraction * item.value) vào totalValue. currentWeight được cập nhật bằng cách thêm đúng remainingCapacity (đảm bảo nó đạt đến capacity). Vì túi đã đầy, chúng ta dùng break để thoát khỏi vòng lặp.
- Hàm trả về totalValue là tổng giá trị tối đa có thể thu được.
main(): Hàm main tạo ra các ví dụ cụ thể về tập hợp các món đồ và dung lượng túi, gọi hàm fractionalKnapsack và in kết quả. Chúng ta có 3 ví dụ để thấy các trường hợp khác nhau: lấy toàn bộ các món đầu tiên, và trường hợp cuối cùng phải lấy một phần.

Ví dụ minh họa chi tiết

Hãy cùng phân tích Ví dụ 1 trong code:

Dung lượng túi: capacity = 50kg.
Các món đồ:
- Item 1: 10kg, $60. Tỉ lệ: $60/10kg = 6$/kg.
- Item 2: 20kg, $100. Tỉ lệ: $100/20kg = 5$/kg.
- Item 3: 30kg, $120. Tỉ lệ: $120/30kg = 4$/kg.

Quá trình giải thuật:

Tính tỉ lệ: Đã tính ở trên: 6, 5, 4.
Sắp xếp: Các món đồ theo tỉ lệ giảm dần: Item 1 (tỉ lệ 6), Item 2 (tỉ lệ 5), Item 3 (tỉ lệ 4).
Điền vào túi:
- Duyệt Item 1 (10kg, $60, ratio 6): Dung lượng còn lại là 50kg. 10kg <= 50kg. Lấy toàn bộ.
  - Trọng lượng hiện tại: 0 + 10 = 10kg.
  - Tổng giá trị: 0 + 60 = $60.
  - Dung lượng còn lại: 50 - 10 = 40kg.
- Duyệt Item 2 (20kg, $100, ratio 5): Dung lượng còn lại là 40kg. 20kg <= 40kg. Lấy toàn bộ.
  - Trọng lượng hiện tại: 10 + 20 = 30kg.
  - Tổng giá trị: 60 + 100 = $160.
  - Dung lượng còn lại: 40 - 20 = 20kg.
- Duyệt Item 3 (30kg, $120, ratio 4): Dung lượng còn lại là 20kg. 30kg > 20kg. Không thể lấy toàn bộ.
  - Tính phần trăm có thể lấy: (dung lượng còn lại) / (trọng lượng món đồ) = 20kg / 30kg = 2/3.
  - Lấy 2/3 của món đồ: trọng lượng = (2/3) 30kg = 20kg, giá trị = (2/3) $120 = $80.
  - Trọng lượng hiện tại: 30 + 20 = 50kg (túi đầy).
  - Tổng giá trị: 160 + 80 = $240.
  - Dung lượng còn lại: 20 - 20 = 0kg.
  - Túi đầy, dừng lại.

Kết quả cuối cùng cho Ví dụ 1 là tổng giá trị tối đa thu được là $240.00$. Output từ chương trình C++ của chúng ta sẽ hiển thị quá trình này và kết quả cuối cùng.

Hãy xem Ví dụ 2:

Dung lượng túi: capacity = 20kg.
Các món đồ:
- Item 1: 5kg, $30. Tỉ lệ: $30/5kg = 6$/kg.
- Item 2: 10kg, $20. Tỉ lệ: $20/10kg = 2$/kg.
- Item 3: 15kg, $45. Tỉ lệ: $45/15kg = 3$/kg.
- Item 4: 2kg, $15. Tỉ lệ: $15/2kg = 7.5$/kg.

Quá trình giải thuật:

Tính tỉ lệ: 6, 2, 3, 7.5.
Sắp xếp: Item 4 (7.5), Item 1 (6), Item 3 (3), Item 2 (2).
Điền vào túi:
- Duyệt Item 4 (2kg, $15, ratio 7.5): Dung lượng còn lại 20kg. 2kg <= 20kg. Lấy toàn bộ.
  - Trọng lượng hiện tại: 0 + 2 = 2kg. Tổng giá trị: 0 + 15 = $15. Dung lượng còn lại: 20 - 2 = 18kg.
- Duyệt Item 1 (5kg, $30, ratio 6): Dung lượng còn lại 18kg. 5kg <= 18kg. Lấy toàn bộ.
  - Trọng lượng hiện tại: 2 + 5 = 7kg. Tổng giá trị: 15 + 30 = $45. Dung lượng còn lại: 18 - 5 = 13kg.
- Duyệt Item 3 (15kg, $45, ratio 3): Dung lượng còn lại 13kg. 15kg > 13kg. Không thể lấy toàn bộ.
  - Phần trăm có thể lấy: 13kg / 15kg = 13/15.
  - Lấy 13/15 của món đồ: trọng lượng = (13/15) 15kg = 13kg, giá trị = (13/15) $45 = $39.
  - Trọng lượng hiện tại: 7 + 13 = 20kg (túi đầy). Tổng giá trị: 45 + 39 = $84.
  - Dung lượng còn lại: 13 - 13 = 0kg.
  - Túi đầy, dừng lại.

Kết quả cuối cùng cho Ví dụ 2 là tổng giá trị tối đa thu được là $84.00$.

Ví dụ 3 cũng hoạt động tương tự, cho thấy lại trường hợp cần lấy một phần của món đồ cuối cùng.

Ứng dụng của Bài toán cái túi phân số

Mặc dù "cái túi" và "món đồ" có vẻ đơn giản, bài toán này mô hình hóa nhiều tình huống thực tế, nơi bạn cần phân bổ một tài nguyên giới hạn để tối đa hóa lợi ích, và tài nguyên đó có thể được chia nhỏ:

Phân bổ tài nguyên sản xuất: Một nhà máy có giờ làm việc giới hạn (dung lượng túi) cần sản xuất nhiều loại sản phẩm khác nhau (món đồ), mỗi loại cần một lượng thời gian nhất định (trọng lượng) và mang lại lợi nhuận khác nhau (giá trị). Nếu có thể sản xuất sản phẩm theo lô nhỏ (phân số), nhà máy sẽ ưu tiên sản phẩm có lợi nhuận/thời gian cao nhất.
Quản lý danh mục đầu tư: Một nhà đầu tư có ngân sách giới hạn (dung lượng túi) muốn đầu tư vào các tài sản khác nhau (món đồ), mỗi tài sản cần một lượng vốn nhất định (trọng lượng - ở đây là vốn) và có tỷ suất lợi nhuận khác nhau (giá trị). Nhà đầu tư sẽ ưu tiên các tài sản có tỷ suất lợi nhuận cao nhất trên mỗi đơn vị vốn.
Lập lịch tác vụ trên CPU: Trong một số trường hợp đơn giản, việc phân bổ thời gian CPU (dung lượng) cho các tác vụ khác nhau (món đồ) có thể được mô hình hóa bằng bài toán này, đặc biệt nếu tác vụ có thể bị tạm dừng và tiếp tục sau (chia nhỏ).
Tải dữ liệu qua băng thông giới hạn: Có nhiều tập tin cần tải (món đồ), mỗi tập có kích thước (trọng lượng) và độ ưu tiên/tầm quan trọng (giá trị) khác nhau. Nếu có thể tải từng phần của tập tin, hệ thống sẽ ưu tiên tải các tập tin có độ ưu tiên cao nhất trên mỗi đơn vị kích thước.

Trong tất cả các trường hợp này, nguyên tắc "tham lam" là luôn ưu tiên tài nguyên (thời gian, vốn, băng thông,...) cho "món đồ" mang lại lợi ích cao nhất trên mỗi đơn vị tài nguyên sử dụng.

Phân tích hiệu suất

Thời gian chạy của thuật toán này chủ yếu phụ thuộc vào bước sắp xếp các món đồ theo tỉ lệ giá trị/trọng lượng. Nếu có $N$ món đồ, việc tính tỉ lệ mất $O(N)$. Việc sắp xếp mất $O(N \log N)$ với các thuật toán sắp xếp hiệu quả như QuickSort hoặc MergeSort (mà std::sort thường sử dụng). Bước điền vào túi chỉ mất $O(N)$ vì chúng ta duyệt qua danh sách đã sắp xếp một lần duy nhất.

Do đó, độ phức tạp thời gian tổng thể của thuật toán giải Bài toán cái túi phân số là $O(N \log N)$, hoàn toàn hiệu quả cho các tập dữ liệu lớn. Độ phức tạp không gian là $O(N)$ để lưu trữ các món đồ và tỉ lệ của chúng.

Bài tập ví dụ:

[Tham Lam]. Nối dây 2.

Cho N sợi dây, biết chi phí nối 2 sợ dây là tổng độ dài của 2 sợi dây đó. Nhiệm vụ của bạn là nối N sợi dây này thành 1 sao cho chi phí nối dây là lớn nhất

Input Format

Dòng 1 chứa số nguyên N; Dòng 2 chứa N số nguyên là độ dài các sợ dây. (1<=N<=10^5; Các sợi dây có độ dài không quá 10^9)

Constraints

Output Format

Đáp án của bài toán chia dư với 10^9 + 7.

Ví dụ:

Dữ liệu vào

6
7 7 6 10 4 8

Dữ liệu ra

Để giải bài toán này nhằm tối đa hóa chi phí nối dây, ta cần áp dụng một chiến lược tham lam ngược với bài toán nối dây truyền thống (tối thiểu hóa).

Hướng giải như sau:

Hiểu bài toán: Chi phí nối hai sợi dây là tổng độ dài của chúng. Mục tiêu là nối tất cả thành một sợi dây duy nhất sao cho tổng chi phí các lần nối là lớn nhất.
Chiến lược Tham lam: Để tổng chi phí lớn nhất, ta muốn các sợi dây có độ dài lớn được cộng vào tổng chi phí nhiều lần nhất có thể. Điều này xảy ra khi các sợi dây dài được tham gia vào các phép nối sớm nhất. Do đó, chiến lược tham lam ở đây là luôn nối hai sợi dây có độ dài lớn nhất hiện có.
Tại sao chiến lược này hiệu quả: Khi ta nối hai sợi dây dài nhất, tổng của chúng (một giá trị lớn) sẽ thay thế hai sợi dây ban đầu và tiếp tục tham gia vào các phép nối sau. Bằng cách này, các giá trị lớn được "nhân lên" qua các bước nối, làm tăng tổng chi phí cuối cùng.
Cấu trúc dữ liệu phù hợp: Để liên tục lấy ra hai phần tử lớn nhất, ta có thể nghĩ đến hàng đợi ưu tiên (priority queue) cực đại. Tuy nhiên, với cách nối hai lớn nhất liên tục, ta nhận thấy một quy luật về số lần mỗi sợi dây ban đầu đóng góp vào tổng chi phí.
Tìm công thức tổng chi phí:
- Sắp xếp N sợi dây ban đầu theo thứ tự giảm dần: a_1 >= a_2 >= ... >= a_N.
- Lần nối đầu tiên: a_1 và a_2. Chi phí: a_1 + a_2. Sợi dây mới có độ dài a_1 + a_2.
- Lần nối thứ hai: (a_1 + a_2) và a_3. Chi phí: (a_1 + a_2) + a_3. Sợi dây mới: a_1 + a_2 + a_3.
- Lần nối thứ ba: (a_1 + a_2 + a_3) và a_4. Chi phí: (a_1 + a_2 + a_3) + a_4. Sợi dây mới: a_1 + a_2 + a_3 + a_4.
- ...
- Lần nối thứ k: (a_1 + ... + a_k) và a_{k+1}. Chi phí: a_1 + ... + a_{k+1}.
- Tổng chi phí là tổng của các chi phí ở mỗi bước: (a_1 + a_2) + (a_1 + a_2 + a_3) + ... + (a_1 + ... + a_N).
- Phân tích sự đóng góp của từng sợi dây ban đầu:
  - a_1 xuất hiện trong tất cả N-1 phép cộng.
  - a_2 xuất hiện trong tất cả N-1 phép cộng.
  - a_3 xuất hiện trong N-2 phép cộng (từ bước 2 trở đi).
  - a_4 xuất hiện trong N-3 phép cộng (từ bước 3 trở đi).
  - ...
  - a_i (với i >= 3) xuất hiện trong N - (i-1) = N - i + 1 phép cộng.
  - a_N xuất hiện trong 1 phép cộng (bước cuối cùng).
- Tổng chi phí = (N-1)a_1 + (N-1)a_2 + (N-2)a_3 + (N-3)a_4 + ... + 1*a_N.
- Tổng chi phí = sum_{i=1 to N} a_i * coeff_i, trong đó coeff_1 = N-1, coeff_2 = N-1, và coeff_i = N-i+1 với i >= 3. (Sử dụng chỉ số 1-based theo a_i)
Lưu ý về tính toán:
- N và độ dài dây có thể lớn, tổng chi phí có thể vượt quá giới hạn của kiểu int. Cần sử dụng kiểu long long.
- Kết quả cuối cùng cần chia dư cho 10^9 + 7. Thực hiện phép chia dư sau mỗi phép cộng và phép nhân để tránh tràn số trung gian.
Các bước thực hiện bằng C++:
- Đọc số nguyên N.
- Đọc N số nguyên là độ dài các sợi dây vào một std::vector<long long>.
- Sắp xếp vector này theo thứ tự giảm dần (std::sort với std::greater<long long>).
- Khởi tạo biến long long total_cost = 0;.
- Định nghĩa hằng số long long MOD = 1e9 + 7;.
- Duyệt qua vector đã sắp xếp (sử dụng chỉ số i từ 0 đến N-1):
  - Xác định hệ số coeff cho phần tử thứ i (0-indexed):
    - Nếu i == 0 hoặc i == 1, coeff = N - 1.
    - Nếu i >= 2, coeff = N - 1 - i. (Kiểm tra lại công thức 0-indexed) Let's use 0-indexed array a[0] >= a[1] >= ... >= a[N-1]. Coeff for a[0]: N-1 Coeff for a[1]: N-1 Coeff for a[2]: N-2 Coeff for a[3]: N-3 ... Coeff for a[i]: N-1-i if i >= 2? No. Coeff for a[i] is N-i. Example N=6: a[0]..a[5]. a[0]: N-1 = 5 a[1]: N-1 = 5 a[2]: N-2 = 4 a[3]: N-3 = 3 a[4]: N-4 = 2 a[5]: N-5 = 1 So, coeff for a[i] (0-indexed) is N-1 if i <= 1, and N-i if i >= 2. This works for all i=0..N-1. If i=0: N-1. If i=1: N-1. If i=2: N-2. If i=N-1 (last element): N-(N-1) = 1. Correct coefficients: N-1 for i=0,1 và N-i cho i >= 2 (0-indexed).
  - Tính toán đóng góp của phần tử hiện tại: long long term = (ropes[i] % MOD * (coeff % MOD)) % MOD; (Chú ý: coeff ở đây là long long N-1 hoặc N-i, nên chỉ cần coeff % MOD nếu coeff có thể vượt quá MOD, nhưng ở đây coeff max là N-1 <= 10^5 nên không cần % MOD cho coeff nếu N nhỏ, nhưng làm vậy cũng không sai). Tốt nhất là long long term = (ropes[i] % MOD * coeff) % MOD; vì coeff là N-1 hoặc N-i sẽ fit trong long long và không vượt MOD nếu N <= 10^5.
  - Cộng vào tổng chi phí: total_cost = (total_cost + term) % MOD;.
- In ra total_cost.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.