Coin Change Problem

如何以最少的硬幣數量來湊出特定金額的錢。

這個問題可以用簡單的方式描述如下：

假設我們有一些不同面額的硬幣，每種面額的硬幣有無限多個，以及一個特定的金額，需要找零。

問題的目標是找到一種方式，使用最少數量的硬幣來湊出該金額的錢。

一般來說，這個問題有兩種主要變體：

最少硬幣數量問題：找出最少數量的硬幣來湊出特定金額。

所有可能的湊零方式問題：找出湊出特定金額的所有可能方式，不一定是最少硬幣數量。

// Coin Change Problem in Kotlin

import java.util.Arrays

class CoinChange {
    fun count(S: IntArray, m: Int, n: Int): Int {
        val table = IntArray(n + 1)
        Arrays.fill(table, 0)
        table[0] = 1
        for (i in 0 until m) {
            for (j in S[i]..n) {
                table[j] += table[j - S[i]]
            }
        }
        return table[n]
    }
}

// main function
fun main(args: Array<String>) {
    val S = intArrayOf(1, 2, 3)
    val m = S.size
    val n = 4
    val cc = CoinChange()
    println(cc.count(S, m, n))
}

Rod Cutting Problem

Rod Cutting Problem 通常用於動態規劃和算法設計中。

這個問題的基本形式是：給定一根固定長度的棒子和不同長度的切割選項，每個切割選項都有一個相應的價值，目標是找到一種切割方法，以最大化切割後各段的價值總和。

具體來說，棒子的長度固定，但您可以選擇在不同位置切割它，每次切割都會消耗一定的成本。

不同的切割選項會給出不同的價值。問題的目標是找到一種切割方式，使得切割後的各段的價值總和最大，考慮到切割成本。

// Rod Cutting Problem in Kotlin
class RodCutting {
    fun cutRod(price: IntArray, n: Int): Int {
        val valArray = IntArray(n + 1)
        valArray[0] = 0
        for (i in 1..n) {
            var maxVal = Integer.MIN_VALUE
            for (j in 0 until i) {
                maxVal = Math.max(maxVal, price[j] + valArray[i - j - 1])
            }
            valArray[i] = maxVal
        }
        return valArray[n]
    }
}

// main function
fun main(args: Array<String>) {
    val arr = intArrayOf(1, 5, 8, 9, 10, 17, 17, 20)
    val size = arr.size
    val rc = RodCutting()
    println("Maximum Obtainable Value is ${rc.cutRod(arr, size)}")
}

所有 Code 可以在 Github 找到 ～

感謝大家，明天見！！！