Longest Increasing Subsequence

Longest Increasing Subsequence 是在一個數字序列中找到一個具有最大長度的子序列，該子序列中的數字按遞增順序排列。

演算法

假設我們有一個數列 nums，長度為n。我們建立一個輔助數組dp，dp[i]表示以nums[i]為結尾的最長遞增子序列的長度。

剛開始我們將dp數組的所有元素初始化為1，因為每個數字本身都可以視為一個長度為1的遞增子序列。

接下來，我們遍歷數列nums，對於每個元素nums[i]，我們再次遍歷在i之前的所有元素nums[j]（j從0到i-1），如果nums[i]大於nums[j]，則更新dp[i]，使其等於dp[j] + 1，表示我們可以將nums[i]添加到以nums[j]結尾的遞增子序列中，並且得到更長的遞增子序列。

我們需要不斷地更新dp數組，直到遍歷完整個數列。

最終，我們可以找到dp數組中的最大值，即最長遞增子序列的長度。

// Long Increasing Subsequence in Kotlin

import java.util.Arrays

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        val dp = IntArray(nums.size)
        var len = 0
        for (num in nums) {
            var i = Arrays.binarySearch(dp, 0, len, num)
            if (i < 0) i = -(i + 1)
            dp[i] = num
            if (i == len) len++
        }
        return len
    }
}

fun main(args: Array<String>) {
    val sol = Solution()
    val nums = intArrayOf(10, 9, 2, 5, 3, 7, 101, 18)
    val res: Int
    res = sol.lengthOfLIS(nums)
    println(res)
}

0-1 Knapsack Problem

在一個給定容量的背包中，有一組物品，每個物品都有一個重量和一個價值。

目標是選擇一組物品，使得它們的總重量不超過背包的容量，同時總價值最大化。

每個物品只能選擇一次，要麼放入背包中，要麼不放入（0-1的選擇），不能將物品分割成更小的部分放入背包。

0-1背包問題的目標是找到一個最佳的組合，以最大化所選物品的總價值，同時保持總重量不超過背包的容量。

// 0-1 Knapsack Problem in Kotlin

// library imports
import java.util.Arrays

class Knapsack {
    fun knapSack(W: Int, wt: IntArray, value: IntArray, n: Int): Int {
        val K = Array(n + 1) { IntArray(W + 1) }
        for (i in 0..n) {
            for (w in 0..W) {
                if (i == 0 || w == 0) {
                    K[i][w] = 0
                } else if (wt[i - 1] <= w) {
                    K[i][w] = Math.max(value[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
                } else {
                    K[i][w] = K[i - 1][w]
                }
            }
        }
        return K[n][W]
    }
}

// main function
fun main(args: Array<String>) {
    val value = intArrayOf(60, 100, 120)
    val wt = intArrayOf(10, 20, 30)
    val W = 50
    val n = value.size
    val knapsack = Knapsack()
    println("Maximum value that can be obtained is ${knapsack.knapSack(W, wt, value, n)}")
}

所有 Code 可以在 Github 找到 ～

感謝大家，明天見！！！

Reference

• Longest increasing subsequence
• Knapsack problem