2024-03-20:用go语言,自 01背包问世之后,小 A 对此深感兴趣。 一天,小 A 去远游,却发现他的背包

2024-03-20:用go语言,自 01背包问世之后,小 A 对此深感兴趣。

一天,小 A 去远游,却发现他的背包不同于 01 背包,他的物品大致可分为 k 组。

每组中的物品只能选择1件,现在他想知道最大的利用价值是多少?

答案2024-03-20:

来自左程云

灵捷3.5

大体步骤如下:

1.定义常量 MAXN 和 MAXM,分别表示物品数量和背包容量的最大值。

2.声明一个二维数组 arr 用于存储物品的重量、价值和组别信息。

3.声明一个一维数组 dp 用于记录每个容量下的最大利用价值。

4.获取输入信息,包括背包容量 m 和物品数量 n。

5.遍历n次,将物品的重量、价值和组别信息存入二维数组 arr。

6.根据物品的组别信息对二维数组 arr 进行排序。

7.初始化数组 dp,将所有元素设置为0。

8.使用动态规划算法计算最大利用价值。遍历每个组别的物品,对于每个容量 r,遍历当前组别的物品,如果容量 r 大于等于物品的重量,则更新 dp[r] 为当前物品的价值加上 dp[r-物品重量] 的最大值。

9.返回 dp[m],即背包容量为 m 时的最大利用价值。

10.打印结果。

总的时间复杂度是 O(nmlog(n)),其中 n 是物品数量,m 是背包容量。这是因为需要对二维数组 arr 进行排序,排序的时间复杂度是 O(nlog(n)),而计算最大利用价值的动态规划算法的时间复杂度是 O(nm)。

总的额外空间复杂度是 O(n),其中 n 是物品数量。这是因为需要使用数组 dp 来记录每个容量下的最大利用价值。

go完整代码如下:

package main

import (
    "fmt"
    "sort"
)

const MAXN = 1001
const MAXM = 1001

var arr = [MAXN][3]int{}
var dp = [MAXM]int{}
var m, n int

func compute() int {
    for start, end := 0, 1; start < n; {
        for end < n && arr[end][2] == arr[start][2] {
            end++
        }
        for r := m; r >= 0; r-- {
            for i := start; i < end; i++ {
                if r >= arr[i][0] {
                    dp[r] = max(dp[r], arr[i][1]+dp[r-arr[i][0]])
                }
            }
        }
        start = end
        end++
    }
    return dp[m]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    inputs := []int{45, 3,
        10, 10, 1,
        10, 5, 1,
        50, 400, 2}
    ii := 0

    m = inputs[ii]
    ii++

    n = inputs[ii]
    ii++

    for i := 0; i < n; i++ {
        arr[i][0] = inputs[ii]
        ii++
        arr[i][1] = inputs[ii]
        ii++
        arr[i][2] = inputs[ii]
        ii++
    }
    sort.Slice(arr[:n], func(i, j int) bool {
        return arr[i][2] < arr[j][2]
    })
    for i := 0; i <= m; i++ {
        dp[i] = 0
    }
    fmt.Println(compute())

}

在这里插入图片描述

python完整代码如下:

# -*-coding:utf-8-*-

MAXN = 1001
MAXM = 1001

arr = [[0] * 3 for _ in range(MAXN)]
dp = [0] * MAXM
m, n = 0, 0

def compute():
    start = 0
    while start < n:
        end = start + 1
        while end < n and arr[end][2] == arr[start][2]:
            end += 1
        for r in range(m, -1, -1):
            for i in range(start, end):
                if r >= arr[i][0]:
                    dp[r] = max(dp[r], arr[i][1] + dp[r - arr[i][0]])
        start = end
    return dp[m]

def max(a, b):
    return a if a > b else b

inputs = [45, 3,
          10, 10, 1,
          10, 5, 1,
          50, 400, 2]
ii = 0

m = inputs[ii]
ii += 1

n = inputs[ii]
ii += 1

for i in range(n):
    arr[i][0] = inputs[ii]
    ii += 1
    arr[i][1] = inputs[ii]
    ii += 1
    arr[i][2] = inputs[ii]
    ii += 1

arr = arr[:n]
arr.sort(key=lambda x: x[2])

for i in range(m + 1):
    dp[i] = 0

print(compute())

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
470
粉丝
21
喜欢
37
收藏
22
排名:457
访问:1.9 万
私信
所有博文
社区赞助商