จำนวนรายการขั้นต่ำที่ต้องส่งมอบต่อเที่ยวด้วย C++

ข้อความโจทย์

กำหนดอาร์เรย์ขนาด N แทนถัง (Buckets) แต่ละดัชนีของอาร์เรย์มีจำนวนรายการ กำหนด K เที่ยวเดินทาง ที่ภายในต้องส่งมอบรายการทั้งหมด สามารถนำรายการจากถังเดียวได้ต่อเที่ยว งานคือบอกจำนวนรายการขั้นต่ำที่ต้องส่งมอบต่อเที่ยว เพื่อให้รายการทั้งหมดสามารถส่งมอบได้ภายใน K เที่ยว

ถ้ามี 5 ถัง ที่มีรายการ = {1, 3, 5, 7, 9} และ 10 เที่ยว แล้วเราสามารถส่งมอบ 3 รายการต่อเที่ยว โดยการส่ง 3 รายการในแต่ละครั้ง -

• ถังที่ 1 ขนาด 1 ดังนั้นเที่ยวที่ต้องการ = 1
• ถังที่ 2 ขนาด 3 ดังนั้นเที่ยวที่ต้องการ = 1
• ถังที่ 3 ขนาด 5 ดังนั้นเที่ยวที่ต้องการ = 2 (3 + 2 รายการต่อเที่ยว)
• ถังที่ 4 ขนาด 7 ดังนั้นเที่ยวที่ต้องการ = 3 (3 + 3 + 1 รายการต่อเที่ยว)
• ถังที่ 5 ขนาด 9 ดังนั้นเที่ยวที่ต้องการ = 3 (3 + 3 + 3 รายการต่อเที่ยว)

จำนวนเที่ยวทั้งหมด = 10

อัลกอริทึม

1. หาจำนวนรายการขั้นต่ำที่ต้องแจกจ่ายต่อการส่งมอบ
2. วนลูปจาก 1 ถึงค่าสูงสุดของรายการในถัง และคำนวณจำนวนเที่ยวที่จำเป็นสำหรับแต่ละถัง และหาจำนวนเที่ยวรวมสำหรับการส่งมอบทั้งหมด
3. ค่าแรกที่ทำให้เที่ยวรวมน้อยกว่าหรือเท่ากับ K ให้จำนวนที่ต้องการ

ตัวอย่างโค้ด

#include <iostream>
#include <climits>
#include <cmath>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int minItemsDeliveried(int *arr, int n, int k) {
    int maxElement = INT_MIN;
    for (int i = 0; i < n; ++i) {
        maxElement = max(maxElement, arr[i]);
    }
    for (int i = 1; i < maxElement + 1; ++i) {
        int tours = 0;
        for (int j = 0; j < n; ++j) {
            if (arr[j] % i == 0) {
                tours += arr[j] / i;
            } else {
                tours += floor(arr[j] / i) + 1;
            }
        }
        if (tours <= k) {
            return i;
        }
    }
    return 1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int k = 10;
    cout << "Minimum items to be delivered = " << minItemsDeliveried(arr, SIZE(arr), k) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum items to be delivered = 3