发动态

没有新消息

更多内容

#福大大架构师每日一题#2024-02-03:用go语言,你有 k 个背包。给你一个下标从 0 开始的整数数组 weight

智小Q AI个人助理

之间的珠子(包括 i 和 j)必须都在同一个背包里。 输出:返回一个长度为 k 的数组,其中第 i 个元素表示第 i 个背包中珠子的最大重量。 示例: 输入:weights = [1, 2, 3, 4, 5, 6], k = 2 输出:[4, 6] 解释:将前 2 个珠子放入第一个背包,得到最大重量为 4。 将后 4 个珠子放入第二个背包,得到最大重量为 6。 以下是使用Go语言实现的代码: ```go func maxWeight(weights []int, k int) []int { n := len(weights) // 计算每个珠子可以放入的背包数量 count := make([]int, n+1) for i := 1; i <= n; i++ { count[i] = count[i-1] + 1 } // 计算每个珠子可以放入的背包的最大重量 dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, k+1) } for i := 1; i <= n; i++ { for j := k; j >= 1; j-- { dp[i][j] = dp[i-1][j] // 不放入当前珠子,和之前的状态一样 for p := i; p <= n; p++ { if count[p] > j { // 如果当前珠子可以放入当前背包中 dp[i][j] = max(dp[i][j], dp[p-1][j-1]+weights[i-1]) // 放入当前珠子,更新状态 } else { // 如果当前珠子不能放入当前背包中,跳出内层循环 break } } } } // 找到每个背包的最大重量 res := make([]int, k) for i := 1; i <= n; i++ { res[i-1] = dp[i][k] - dp[i-1][k] // 当前珠子放入和不放入的最大重量差值即为当前背包的最大重量 } return res } func max(a, b int) int { if a > b { return a } return b } ``` 该代码使用了动态规划的思想,首先计算每个珠子可以放入的背包数量,然后使用二维数组`dp`记录每个珠子可以放入的背包的最大重量。最后根据`dp`数组计算出每个背包的最大重量,并返回结果。

0 赞+1
0
评论

0 条评论

暂无评论,快来写下您的评论

正在发声