2024-01-27：用 go 语言，阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N 堆金币，第 i 堆金币的总重量和总价值分别是 m[i]、v[i]，阿里巴巴有一个承重量为 T 的背包，但并不一定有办法将全部的

作者：福大大架构师每日一题

2024-01-27
北京
本文字数：1348 字
阅读完需：约 4 分钟

2024-01-27：用 go 语言，阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N 堆金币，

第 i 堆金币的总重量和总价值分别是 m[i]、v[i]，

阿里巴巴有一个承重量为 T 的背包，但并不一定有办法将全部的金币都装进去，

他想装走尽可能多价值的金币，

所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。

请问阿里巴巴最多可以拿走多少价值的金币？

答案 2024-01-27：

来自左程云。

灵捷3.5

大体过程如下：

1.初始化变量和输入数据：

声明常量 MAXN，并赋值为 101。
定义二维数组 mv，大小为 [MAXN][2]，用于存储金币的重量和价值。
定义变量 n 和 t，分别表示金币堆数和背包的最大承重。
初始化输入数据 inputs 和指针变量 ii。

2.读取金币堆的重量和价值：

使用循环从输入数据中读取金币堆的重量和价值，并将其存储到数组 mv 中。

3.按照单位价格进行排序：

使用 sort.Slice 函数对 mv 数组进行排序，排序规则为单位价格从高到低。

4.背包装金币：4.1.初始化变量 ans（总价值）为 0.0，used（已使用的背包承重）为 0。4.2.使用循环遍历金币堆：

4.2.1.若将当前金币堆放入背包不超过最大承重，则将其重量累加到 used，价值累加到 ans。

4.2.2.否则跳出循环。

4.3.如果跳出循环前仍有剩余的金币堆：

4.3.1.计算剩余空间可以容纳的金币部分的比例（剩余承重 / 剩余金币堆重量）。

4.3.2.将该比例乘以剩余金币堆的价值，累加到 ans。

5.输出结果：

使用 fmt.Printf 函数打印 ans，保留两位小数。

总的时间复杂度为 O(n log n)，其中 n 是金币堆的数量。这是因为排序操作的时间复杂度为 O(n log n)。

总的额外空间复杂度为 O(1)，因为除了输入数据和一个固定大小的数组，没有使用额外的空间。

go 完整代码如下：

package main
import (  "fmt"  "sort")
const MAXN = 101
var mv [MAXN][2]intvar n, t int
func main() {  inputs := []int{4, 50,    10, 60,    20, 100,    30, 120,    15, 45}  ii := 0
  n = inputs[ii]  ii++  t = inputs[ii]  ii++
  for i := 0; i < n; i++ {    mv[i][0] = inputs[ii]    ii++    mv[i][1] = inputs[ii]    ii++  }
  sort.Slice(mv[:n], func(i, j int) bool {    return mv[j][1]*mv[i][0] < mv[i][1]*mv[j][0]  })
  ans := 0.0  used := 0  i := 0  for i = 0; i < n && used+mv[i][0] <= t; i++ {    used += mv[i][0]    ans += float64(mv[i][1])  }  if i < n {    ans += float64(mv[i][1]) * float64(t-used) / float64(mv[i][0])  }  fmt.Printf("%.2f\n", ans)
}

复制代码

python 完整代码如下：

# -*-coding:utf-8-*-
MAXN = 101
inputs = [4, 50,          10, 60,          20, 100,          30, 120,          15, 45]ii = 0
n = inputs[ii]ii += 1t = inputs[ii]ii += 1
mv = [[0, 0] for _ in range(MAXN)]
for i in range(n):    mv[i][0] = inputs[ii]    ii += 1    mv[i][1] = inputs[ii]    ii += 1
mv.sort(key=lambda x: x[1]*x[0] < x[0]*x[1], reverse=True)
ans = 0.0used = 0i = 0for i in range(n):    if used + mv[i][0] <= t:        used += mv[i][0]        ans += mv[i][1]    else:        break
if i < n:    ans += mv[i][1] * (t - used) / mv[i][0]
print("{:.2f}".format(ans))