searchusermenu
  • 发布文章
  • 消息中心
点赞
收藏
评论
分享
原创

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

2024-01-29 02:33:22
1
0
2024-01-27:用go语言,阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有N堆金币,
 
第i堆金币的总重量和总价值分别是m[i]、v[i],
 
阿里巴巴有一个承重量为T的背包,但并不一定有办法将全部的金币都装进去,
 
他想装走尽可能多价值的金币,
 
所有金币都可以随意分割,分割完的金币重量价值比(也就是单位价格)不变。
 
请问阿里巴巴最多可以拿走多少价值的金币?
 
答案2024-01-27:
 
# 大体过程如下:
 
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完整代码如下:
 
```go
package main
 
import (
"fmt"
"sort"
)
 
const MAXN = 101
 
var mv [MAXN][2]int
var 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完整代码如下:
 
```python
# -*-coding:utf-8-*-
 
MAXN = 101
 
inputs = [4, 50,
          10, 60,
          20, 100,
          30, 120,
          15, 45]
ii = 0
 
n = inputs[ii]
ii += 1
t = 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.0
used = 0
i = 0
for 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))
 
 
```
 

 

0条评论
0 / 1000
3****m
116文章数
2粉丝数
3****m
116 文章 | 2 粉丝
原创

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

2024-01-29 02:33:22
1
0
2024-01-27:用go语言,阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有N堆金币,
 
第i堆金币的总重量和总价值分别是m[i]、v[i],
 
阿里巴巴有一个承重量为T的背包,但并不一定有办法将全部的金币都装进去,
 
他想装走尽可能多价值的金币,
 
所有金币都可以随意分割,分割完的金币重量价值比(也就是单位价格)不变。
 
请问阿里巴巴最多可以拿走多少价值的金币?
 
答案2024-01-27:
 
# 大体过程如下:
 
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完整代码如下:
 
```go
package main
 
import (
"fmt"
"sort"
)
 
const MAXN = 101
 
var mv [MAXN][2]int
var 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完整代码如下:
 
```python
# -*-coding:utf-8-*-
 
MAXN = 101
 
inputs = [4, 50,
          10, 60,
          20, 100,
          30, 120,
          15, 45]
ii = 0
 
n = inputs[ii]
ii += 1
t = 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.0
used = 0
i = 0
for 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))
 
 
```
 

 

文章来自个人专栏
福大大架构师每日一题
116 文章 | 1 订阅
0条评论
0 / 1000
请输入你的评论
0
0