Job Sequencing Problem

Job Sequencing Problem 是一個排程問題，通常在生產和製造領域中遇到。目標是在有限的時間內，安排一組工作（或任務）以最大化總利潤或完成工作的數量。

問題描述如下：有一組工作，每個工作都有一個指定的利潤，以及一個必須完成工作的截止日期。這些工作需要按照某種順序執行，並且不能同時執行多個工作。問題的目標是找到一個執行順序，以最大化總利潤或最大程度滿足截止日期。

Job Sequencing Problem 通常有以下幾種類型：

1. 單機排程問題：只有一台機器可用，並且每個工作的執行時間不同。目標是最大化總利潤或滿足截止日期。

2. 平行機排程問題：有多台機器可用，每個工作都可以在其中一台機器上執行，並且每台機器的執行速度可能不同。目標是找到一個執行順序，以最大化總利潤或滿足截止日期。

3. 截止日期約束排程問題：每個工作都有一個嚴格的截止日期，必須在該日期之前完成。目標是最大化總利潤，同時滿足所有截止日期。

// Job Sequencing Problem in Kotlin

import java.util.Arrays
import java.util.Comparator

class Job(var id: Char, var deadline: Int, var profit: Int)

class JobSequencing {
    fun printJobScheduling(arr: Array<Job>, t: Int) {
        // length of array
        val n = arr.size
        // Sort all jobs according to decreasing order of profit
        Arrays.sort(arr, Comparator.comparingInt { obj: Job -> obj.profit }.reversed())
        // To keep track of free time slots
        val result = IntArray(t)
        // To store result (Sequence of jobs)
        val job = BooleanArray(t)
        // Iterate through all given jobs
        var i = 0
        while (i < n) {
            // Find a free slot for this job (Note that we start
            // from the last possible slot)
            var j = Math.min(t - 1, arr[i].deadline - 1)
            while (j >= 0) {
                // Free slot found
                if (!job[j]) {
                    result[j] = i // Add this job to result
                    job[j] = true // Make this slot occupied
                    break
                }
                j--
            }
            i++
        }
        // Print the result
        for (k in 0 until t) if (job[k]) println(arr[result[k]].id)
    }
}

// main function
fun main(args: Array<String>) {
    val arr = arrayOf(
        Job('a', 2, 100),
        Job('b', 1, 19),
        Job('c', 2, 27),
        Job('d', 1, 25),
        Job('e', 3, 15)
    )
    val t = 3
    val js = JobSequencing()
    js.printJobScheduling(arr, t)
}

Fractional Knapsack Problem

Fractional Knapsack Problem 是一個組合優化問題，通常出現在資源分配和最佳化問題中。

目標是在有限的容量下，選擇一組物品，以最大化其總價值。

演算法

有一個固定容量的背包，以及一組物品，每個物品都有一個指定的重量和價值。

背包的容量有限，不能容納無限多的物品。目標是選擇一些物品放入背包中，使得它們的總重量不超過背包容量，同時最大化所選物品的總價值。

分數背包問題的特點是，我們可以部分地選擇一個物品，即將物品分成更小的部分放入背包中。

Difference between 0-1 Knapsack Problem

我們可以根據物品的價值密度（每單位重量的價值）來選擇部分物品，而不僅僅是選擇整個物品。

按照物品的價值密度（價值除以重量）降序排列物品，然後依次選擇價值密度最高的物品放入背包，直到背包容量不足或所有物品都被選擇。

分數背包問題的目標是找到一個最優策略，以在有限的背包容量下獲得最大價值。

// Fractional Knapsack Problem in Kotlin

data class Item(val weight: Double, val value: Double)

fun fractionalKnapsack(items: List<Item>, capacity: Double): Double {
    // Sort items by value density (value/weight) in descending order
    val sortedItems = items.sortedByDescending { it.value / it.weight }
    
    var currentWeight = 0.0
    var totalValue = 0.0
    
    for (item in sortedItems) {
        if (currentWeight + item.weight <= capacity) {
            // Add the whole item to the knapsack
            currentWeight += item.weight
            totalValue += item.value
        } else {
            // Add a fraction of the item to fill the remaining capacity
            val remainingCapacity = capacity - currentWeight
            val fraction = remainingCapacity / item.weight
            totalValue += fraction * item.value
            break
        }
    }
    
    return totalValue
}

fun main() {
    val items = listOf(
        Item(10.0, 60.0),
        Item(20.0, 100.0),
        Item(30.0, 120.0)
    )
    val capacity = 50.0
    
    val maxValue = fractionalKnapsack(items, capacity)
    println("Maximum value in the knapsack: $maxValue")
}

所有 Code 可以在 Github 找到 ～

感謝大家，明天見！！！