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]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完整代碼如下：

# -*-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))

在這裡插入圖片描述