仓颉语言实现分数背包问题解析

分数背包问题是一种经典的优化问题，允许物品被分割装入背包。以下代码使用仓颉语言实现了该算法，包含核心逻辑和辅助函数。

核心数据结构与类定义

定义Item类表示背包中的物品，包含重量和价值属性：

class Item {
    public let weight: Float64
    public let value: Float64

    public init(weight: Float64, value: Float64) {
        this.weight = weight
        this.value = value
    }
}

单位价值计算函数

计算物品的单位价值（价值/重量），处理零重量特殊情况：

func get_unit_value(item: Item): Float64 {
    if (item.weight == 0.0) {
        return 0.0
    }
    return item.value / item.weight
}

物品排序实现

通过冒泡排序按单位价值降序排列物品列表：

func sort_by_unit_value(items: ArrayList<Item>): ArrayList<Item> {
    let size = items.size
    var result = ArrayList<Item>()
    
    for (i in 0..size) {
        result.add(items[i])
    }
    
    for (i in 0..size) {
        for (j in i+1..size) {
            let unit_i = get_unit_value(result[i])
            let unit_j = get_unit_value(result[j])
            if (unit_i < unit_j) {
                var temp = result[i]
                result[i] = result[j]
                result[j] = temp
            }
        }
    }
    
    return result
}

分数背包算法主体

实现贪心算法解决分数背包问题：

func fractional_knapsack(capacity: Float64, items: ArrayList<Item>): Float64 {
    var sorted_items = sort_by_unit_value(items)

    var total_value: Float64 = 0.0
    var remaining: Float64 = capacity

    for (item in sorted_items) {
        if (remaining <= 0.0) {
            break
        }

        if (item.weight <= remaining) {
            total_value += item.value
            remaining -= item.weight
        } else {
            let take_ratio = remaining / item.weight
            total_value += item.value * take_ratio
            remaining = 0.0
        }
    }

    return total_value
}

辅助函数实现

包含字符串到数值的转换工具函数：

func string_to_int64(s: String): Int64 {
    var result: Int64 = 0
    var sign: Int64 = 1
    var i: Int64 = 0
    
    if (s.size > 0) {
        let first = s[0]
        if (first == 45) {
            sign = -1
            i = 1
        }
    }
    
    while (i < s.size) {
        let ch = s[i]
        if (ch >= 48 && ch <= 57) {
            result = result * 10
            if (ch == 48) {}
            else if (ch == 49) { result = result + 1 }
            else if (ch == 50) { result = result + 2 }
            // ...其他数字处理
        }
        i++
    }
    
    return result * sign
}

实现浮点数解析函数：

func string_to_float64(s: String): Float64 {
    var result: Float64 = 0.0
    var decimal: Float64 = 0.0
    var decimal_div: Float64 = 1.0
    var sign: Float64 = 1.0
    var i: Int64 = 0
    var in_decimal = false
    
    // 处理符号位
    if (s.size > 0) {
        let first = s[0]
        if (first == 45) {
            sign = -1.0
            i = 1
        }
    }
    
    // 解析整数和小数部分
    while (i < s.size) {
        let ch = s[i]
        if (ch == 46) {
            in_decimal = true
        } else if (ch >= 48 && ch <= 57) {
            // 数字字符处理
        }
        i++
    }
    
    return (result + decimal) * sign
}

输入输出处理

实现字符到字符串的转换：

func rune_to_string(ch: Rune): String {
    var s = String()
    match (ch) {
        case '0' => s = "0"
        // 其他字符处理...
        case _ => s = ""
    }
    return s
}

实现标准输入读取功能：

func readLine(): String {
    var result = String()
    var running = true
    while (running) {
        let opt = Console.stdIn.read()
        match (opt) {
            case Some(ch) =>
                match (ch) {
                    case '\n' =>
                        running = false
                    case '\r' => ()
                    case _ =>
                        result = result + rune_to_string(ch)
                }
            case None =>
                running = false
        }
    }
    return result
}

算法特点与应用

该实现展示了仓颉语言的特性：

• 强类型系统（Float64/Int64明确声明）
• 模式匹配（match语法）
• 面向对象与函数式混合范式
• 显式的空值处理（Option类型）

典型应用场景包括资源分配、投资组合优化等需要最大化价值/重量比的场景。算法时间复杂度主要由排序步骤决定，通常为O(n²)。