算法输出

简介

分数背包问题（Fractional Knapsack Problem）是背包问题的一个变种。与 0/1 背包不同，分数背包允许将物品分割成任意大小的片段。这意味着我们可以选择物品的一部分而不是整个物品。

分数背包问题的特点：

• 物品可以分割
• 目标是最大化背包内物品的总价值
• 背包容量有限制
• 使用贪心算法可以得到最优解

算法原理详解

核心思想

分数背包的贪心策略基于以下观察：

• 计算每个物品的价值/重量比（单位价值）
• 按单位价值从高到低排序
• 优先选择单位价值最高的物品
• 如果物品无法完全放入，则选择部分物品

为什么贪心策略有效

证明思路：

1. 假设最优解中包含单位价值较低的物品
2. 将其替换为单位价值较高的物品
3. 由于单位价值更高，替换后的解更优
4. 因此贪心选择是安全的

与 0/1 背包的区别

特性	0/1 背包	分数背包
物品分割	不可分割	可分割
求解方法	动态规划	贪心算法
时间复杂度	O(nW)	O(n log n)
最优性	贪心不一定最优	贪心一定最优

第一步：Kotlin 中实现分数背包

基础实现

data class Item(val id: Int, val value: Int, val weight: Int)

fun fractionalKnapsack(capacity: Int, items: List<Item>): Double {
    // 按单位价值（价值/重量）从高到低排序
    val sorted = items.sortedByDescending { it.value.toDouble() / it.weight }
    var totalValue = 0.0
    var remainingCapacity = capacity
    
    for (item in sorted) {
        if (remainingCapacity >= item.weight) {
            // 物品可以完全放入
            totalValue += item.value
            remainingCapacity -= item.weight
        } else {
            // 物品只能部分放入
            totalValue += item.value * remainingCapacity.toDouble() / item.weight
            break
        }
    }
    
    return totalValue
}

代码说明：

• 使用数据类表示物品
• 按单位价值排序
• 优先选择单位价值最高的物品
• 如果物品无法完全放入，选择部分物品

详细实现（返回选择方案）

data class Selection(val itemId: Int, val fraction: Double, val value: Double)

fun fractionalKnapsackDetailed(capacity: Int, items: List<Item>): Pair<List<Selection>, Double> {
    val sorted = items.sortedByDescending { it.value.toDouble() / it.weight }
    val selections = mutableListOf<Selection>()
    var totalValue = 0.0
    var remainingCapacity = capacity
    
    for (item in sorted) {
        if (remainingCapacity <= 0) break
        
        if (remainingCapacity >= item.weight) {
            // 完全选择
            selections.add(Selection(item.id, 1.0, item.value.toDouble()))
            totalValue += item.value
            remainingCapacity -= item.weight
        } else {
            // 部分选择
            val fraction = remainingCapacity.toDouble() / item.weight
            val value = item.value * fraction
            selections.add(Selection(item.id, fraction, value))
            totalValue += value
            remainingCapacity = 0
        }
    }
    
    return Pair(selections, totalValue)
}

贪心选择过程示例

fun demonstrateFractionalKnapsack() {
    val items = listOf(
        Item(1, 60, 10),  // 单位价值: 6
        Item(2, 100, 20), // 单位价值: 5
        Item(3, 120, 30)  // 单位价值: 4
    )
    val capacity = 50
    
    val (selections, totalValue) = fractionalKnapsackDetailed(capacity, items)
    
    println("分数背包问题演示:")
    println("背包容量: $capacity")
    println("选择方案:")
    selections.forEach { (itemId, fraction, value) ->
        println("  物品$itemId: 选择 ${fraction * 100}%, 价值 $value")
    }
    println("总价值: $totalValue")
}

第二步：导出为 JavaScript

@JsExport
fun runBatch5() {
    val items = listOf(
        Item(1, 60, 10),
        Item(2, 100, 20),
        Item(3, 120, 30)
    )
    val capacity = 50
    
    val (selections, totalValue) = fractionalKnapsackDetailed(capacity, items)
    
    println("分数背包问题:")
    println("物品列表:")
    items.forEach { item ->
        println("  物品${item.id}: 价值${item.value}, 重量${item.weight}, 单位价值${item.value.toDouble() / item.weight}")
    }
    println("背包容量: $capacity")
    println("选择方案: $selections")
    println("最大价值: $totalValue")
}

第三步：编译为 JavaScript

./gradlew jsJar

第四步：在 OpenHarmony 中调用

const algorithms: Algorithm[] = [
  { 
    id: 23, 
    name: '分数背包', 
    nameEn: 'Fractional Knapsack', 
    category: '贪心', 
    description: '可分割背包' 
  },
];

第五步：执行算法

case 23:
  output = `【分数背包问题】\n物品: [(60,10), (100,20), (120,30)]\n背包容量: 50\n价值/重量比: [6, 5, 4]\n选择方案: 全选物品1,2,部分物品3\n最大价值: 60+100+40 = 200\n填充率: 100%`;
  break;

完整工作流程

Kotlin 代码 (fractionalKnapsack)
    ↓
@JsExport 注解
    ↓
KMP 编译 (./gradlew jsJar)
    ↓
JavaScript 文件 (kjsdemo.js)
    ↓
OpenHarmony 应用导入
    ↓
ArkTS 调用 (console.log)
    ↓
控制台输出结果

实际应用场景

1. 液体混合问题

容器容量: 100 升
液体A: 价值 60 元/升, 可用 10 升
液体B: 价值 50 元/升, 可用 20 升
液体C: 价值 40 元/升, 可用 30 升

最优方案: 全选 A 和 B，部分选 C

2. 资源分配

总资源: 100 单位
项目A: 收益 60/单位, 需要 10 单位
项目B: 收益 50/单位, 需要 20 单位
项目C: 收益 40/单位, 需要 30 单位

3. 投资组合

总资金: 10,000 元
投资A: 年收益 6%, 最多投 1,000 元
投资B: 年收益 5%, 最多投 2,000 元
投资C: 年收益 4%, 最多投 3,000 元

性能分析

指标	值
时间复杂度	O(n log n)
空间复杂度	O(n)
排序时间	O(n log n)
选择时间	O(n)
最坏情况	O(n log n)

优化建议

1. 预排序：如果物品已按单位价值排序，可跳过排序
2. 流式处理：对大规模数据使用流式处理
3. 并行化：可并行处理多个背包问题
4. 缓存：缓存排序结果以加速后续查询

总结

分数背包问题是贪心算法的经典应用，通过 KMP 和 OpenHarmony 的结合，我们可以：

• 在 Kotlin 中实现高效的分数背包算法
• 自动编译为 JavaScript
• 在 OpenHarmony 应用中无缝调用
• 在控制台查看实时输出

这个算法在实际应用中非常有用，特别是在资源分配和投资决策领域。

---

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net