โปรแกรม C++ นับจำนวนเหรียญขั้นต่ำเพื่อให้ได้ค่า N ด้วยการคูณและบวกลบ

คำอธิบายปัญหา

สมมติว่าเรามีตัวเลข 5 ตัวคือ N, A, B, C, D เริ่มจากเลข 0 และต้องการไปถึง N สามารถเปลี่ยนแปลงตัวเลขได้โดยจ่ายเหรียญตามการดำเนินการต่อไปนี้:

• คูณตัวเลขด้วย 2 จ่าย A เหรียญ
• คูณตัวเลขด้วย 3 จ่าย B เหรียญ
• คูณตัวเลขด้วย 5 จ่าย C เหรียญ
• เพิ่มหรือลดตัวเลขลง 1 จ่าย D เหรียญ

สามารถทำซ้ำได้ไม่จำกัดครั้งและสลับลำดับได้ ต้องการหาจำนวนเหรียญน้อยที่สุดเพื่อให้ได้ N

ตัวอย่าง: N = 11; A = 1; B = 2; C = 2; D = 8 ผลลัพธ์คือ 19 โดยกระบวนการ:

• จ่าย 8 เหรียญ เพิ่ม 1 (x=1)
• จ่าย 1 เหรียญ คูณ 2 (x=2)
• จ่าย 2 เหรียญ คูณ 5 (x=10)
• จ่าย 8 เหรียญ เพิ่ม 1 (x=11)

ขั้นตอนการแก้ปัญหา

กำหนด map f สำหรับ key และ value แบบ integer
กำหนด map vis สำหรับ key แบบ integer และ value แบบ Boolean
กำหนดฟังก์ชัน calc รับ n:
    ถ้า n เป็นศูนย์: คืนค่า 0
    ถ้า n อยู่ใน vis: คืนค่า f[n]
    vis[n] := 1
    res := calc(n / 2) + n mod 2 * d + a
    ถ้า n mod 2 ไม่เป็นศูนย์:
        res := min(res, calc(n / 2 + 1) + (2 - n mod 2) * d + a)
    res := min(res, calc(n / 3) + n mod 3 * d + b)
    ถ้า n mod 3 ไม่เป็นศูนย์:
        res := min(res, calc(n / 3 + 1) + (3 - n mod 3) * d + b)
    res := min(res, calc(n / 5) + n mod 5 * d + c)
    ถ้า n mod 5 ไม่เป็นศูนย์:
        res := min(res, calc(n / 5 + 1) + (5 - n mod 5) * d + c)
    ถ้า (res - 1) / n + 1 > d:
        res := n * d
    คืนค่า f[n] = res
จาก main เรียก calc(n)

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

#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;
map<long, long> f;
map<long, bool> vis;

long calc(long n){
    if (!n) return 0;
    if (vis.find(n) != vis.end()) return f[n];
    vis[n] = 1;
    long res = calc(n / 2) + n % 2 * d + a;
    if (n % 2) res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a);
    res = min(res, calc(n / 3) + n % 3 * d + b);
    if (n % 3) res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b);
    res = min(res, calc(n / 5) + n % 5 * d + c);
    if (n % 5) res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c);
    if ((res - 1) / n + 1 > d) res = n * d;
    return f[n] = res;
}

int solve(int N, int A, int B, int C, int D){
    a = A; b = B; c = C; d = D;
    return calc(N);
}

int main(){
    int N = 11;
    int A = 1;
    int B = 2;
    int C = 2;
    int D = 8;
    cout << solve(N, A, B, C, D) << endl;
}

อินพุต

11, 1, 2, 2, 8

เอาต์พุต

19