算法输出

简介

0/1 背包问题是经典的动态规划问题，目标是在背包容量限制下，选择物品使得总价值最大。本文将展示如何使用 Kotlin Multiplatform (KMP) 实现背包问题，并通过 JavaScript 编译后在 OpenHarmony 应用中调用。

算法原理

背包问题的核心思想：

• 每个物品可以选择放入或不放入背包
• 使用动态规划计算最大价值
• 构建二维 DP 表格
• 时间复杂度：O(n × W)
• 空间复杂度：O(n × W)

第一步：Kotlin 中实现背包问题

在 shared/src/commonMain/kotlin/Batch3_DynamicProgramming.kt 中实现背包问题：

fun knapsack(weights: IntArray, values: IntArray, capacity: Int): Int {
    val n = weights.size
    val dp = Array(n + 1) { IntArray(capacity + 1) }
    
    for (i in 1..n) {
        for (w in 0..capacity) {
            if (weights[i - 1] <= w) {
                dp[i][w] = maxOf(
                    dp[i - 1][w],  // 不放入
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]  // 放入
                )
            } else {
                dp[i][w] = dp[i - 1][w]
            }
        }
    }
    
    return dp[n][capacity]
}

代码说明：

• dp[i][w] 表示前 i 个物品，背包容量为 w 时的最大价值
• 对每个物品，决定是否放入背包
• 选择能获得更大价值的方案
• 返回 dp[n][capacity] 作为最终结果

第二步：导出为 JavaScript

使用 @JsExport 注解将 Kotlin 函数导出为 JavaScript：

@JsExport
fun runBatch3() {
    val weights = intArrayOf(2, 3, 4, 5)
    val values = intArrayOf(3, 4, 5, 6)
    val capacity = 5
    
    println("物品重量: ${weights.joinToString(", ")}")
    println("物品价值: ${values.joinToString(", ")}")
    println("背包容量: $capacity")
    
    val maxValue = knapsack(weights, values, capacity)
    println("最大价值: $maxValue")
}

导出说明：

• @JsExport 注解使函数可以从 JavaScript 中调用
• 返回最大价值
• println() 输出到控制台

第三步：编译为 JavaScript

在项目根目录执行编译命令：

./gradlew jsJar

编译完成后，会生成 build/js/packages/kjsdemo/kotlin/kjsdemo.js 文件。

编译过程说明：

• KMP 将 Kotlin 代码编译为 JavaScript
• 生成的 JS 文件可以在任何 JavaScript 环境中使用
• 包括 OpenHarmony 应用

第四步：在 OpenHarmony 中调用

在 kmp_ceshiapp/entry/src/main/ets/pages/Index.ets 中定义算法列表：

const algorithms: Algorithm[] = [
  { 
    id: 9, 
    name: '背包问题', 
    nameEn: 'Knapsack', 
    category: '动态规划', 
    description: '经典DP问题' 
  },
  // ... 其他算法
];

列表说明：

• 每个算法都有唯一的 ID
• 包含中文名称、英文名称、分类和描述
• 点击列表项会导航到详情页面

第五步：执行算法并输出到控制台

在 kmp_ceshiapp/entry/src/main/ets/pages/AlgorithmDetail.ets 中处理算法执行：

executeAlgorithm() {
  let output = '';
  
  switch (this.algorithmId) {
    case 9:
      output = `背包问题:\n物品重量: [2, 3, 4, 5]\n物品价值: [3, 4, 5, 6]\n背包容量: 5\n最大价值: 10`;
      break;
    // ... 其他算法
  }
  
  // 输出到控制台
  console.log(`========== ${this.algorithmName} (${this.algorithmNameEn}) ==========`);
  console.log(`分类: ${this.algorithmCategory}`);
  console.log(`描述: ${this.algorithmDesc}`);
  console.log(`结果:\n${output}`);
  console.log('='.repeat(50));
  
  // 延迟后返回
  setTimeout(() => {
    router.back();
  }, 500);
}

执行说明：

• 根据算法 ID 执行对应的算法
• 使用 console.log() 输出结果到控制台
• 自动返回到算法列表

完整工作流程

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

测试步骤

1. 编译项目

   cd D:\flutter_Obj\kjsdemo-master
   ./gradlew jsJar
   

2. 构建 OpenHarmony 应用

   cd kmp_ceshiapp
   hvigor build
   

3. 运行应用

   • 在 OpenHarmony 模拟器或真机上运行应用
   • 点击"背包问题"算法
   • 在控制台查看输出结果

预期输出

========== 背包问题 (Knapsack) ==========
分类: 动态规划
描述: 经典DP问题
结果:
背包问题:
物品重量: [2, 3, 4, 5]
物品价值: [3, 4, 5, 6]
背包容量: 5
最大价值: 10
==================================================

性能分析

指标	值
时间复杂度	O(n × W)
空间复杂度	O(n × W)
空间优化	O(W)
最坏情况	O(n × W)

优化建议

1. 空间优化：使用一维数组替代二维数组，空间复杂度可降低到 O(W)
2. 多重背包：每个物品可以选择多个
3. 完全背包：每个物品可以无限选择

总结

通过 KMP 和 OpenHarmony 的结合，我们可以：

• 在 Kotlin 中编写经典的动态规划算法
• 自动编译为 JavaScript
• 在 OpenHarmony 应用中无缝调用
• 在控制台查看实时输出

背包问题是动态规划的典型应用，广泛用于资源分配、投资决策等领域。

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