仓颉解决“分数背包问题”

仓颉语言实现分数背包问题解析分数背包问题是一种经典的优化问题允许物品被分割装入背包。以下代码使用仓颉语言实现了该算法包含核心逻辑和辅助函数。核心数据结构与类定义定义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: ArrayListItem): ArrayListItem { let size items.size var result ArrayListItem() for (i in 0..size) { result.add(items[i]) } for (i in 0..size) { for (j in i1..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: ArrayListItem): 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²)。