文心一言 VS 讯飞星火 VS chatgpt （215）-- 算法导论16.2 2题
二、设计动态规划算法求解 0-1 背包问题，要求运行时间为 O(nW)，n为商品数量，W是小偷能放进背包的最大商品总重量。如果要写代码，请用go语言。
文心一言：
0-1 背包问题是一个典型的动态规划问题，其目标是在给定的重量限制下最大化背包中物品的总价值。每个物品可以选择放入背包或不放入背包（0-1表示），并且每种物品只有一个。
为了设计满足 O(nW) 时间复杂度的算法，我们可以使用二维数组 dp[i][w] 来存储子问题的解，其中 i 表示考虑的物品数量，w 表示当前的重量限制。dp[i][w] 表示考虑前 i 个物品且重量不超过 w 的情况下能得到的最大价值。
下面是使用 Go 语言实现的代码：
package?main
import?(
"fmt"
)
//?Max?returns?the?larger?of?x?or?y.
func?Max(x,?y?int)?int?{
if?x?>?y?{
return?x
}
return?y
}
//?ZeroOneKnapsack?解决?0-1?背包问题
func?ZeroOneKnapsack(weights?[]int,?values?[]int,?W?int)?int?{
n?:=?len(weights)
dp?:=?make([][]int,?n+1)
for?i?:=?range?dp?{
dp[i]?=?make([]int,?W+1)
}
for?i?:=?1;?i?<=?n;?i++?{
for?w?:=?1;?w?<=?W;?w++?{
if?weights[i-1]?<=?w?{
//?当前物品可以放入背包，考虑放入和不放入两种情况
dp[i][w]?=?Max(dp[i-1][w],?dp[i-1][w-weights[i-1]]+values[i-1])
}?else?{
//?当前物品不能放入背包，只考虑不放入的情况
dp[i][w]?=?dp[i-1][w]
}
}
}
//?背包的最大价值即为?dp[n][W]
return?dp[n][W]
}
func?main()?{
weights?:=?[]int{2,?3,?4,?5}??//?商品重量
values?:=?[]int{3,?4,?5,?6}??//?商品价值
W?:=?5????????????????????????//?背包最大承重
maxValue?:=?ZeroOneKnapsack(weights,?values,?W)
fmt.Printf("The?maximum?value?that?can?be?put?in?a?knapsack?of?capacity?%d?is?%d\n",?W,?maxValue)
}
这个算法的时间复杂度是 O(nW)，因为我们需要遍历所有的物品（n个）和所有可能的重量（W个）。空间复杂度也是 O(nW)，因为我们需要一个二维数组来存储中间结果。
注意，在实际应用中，可以通过优化来减少空间复杂度。例如，我们可以使用一维数组 dp[w] 来代替二维数组 dp[i][w]，因为当前状态 dp[i][w] 只依赖于前一个状态 dp[i-1][w] 和 dp[i-1][w-weights[i-1]]。这样的优化通常称为“滚动数组”优化，可以将空间复杂度降低到 O(W)。不过，在这里为了保持算法描述的清晰性，我们使用了二维数组。
在这里插入图片描述
在这里插入图片描述在这里插入图片描述讯飞星火：
0-1背包问题是一个经典的动态规划问题。在这个问题中，我们有n个商品，每个商品i有一个价值vi和一个重量wi。我们的目标是选择一些商品放入背包，使得总价值最大，同时保证总重量不超过W。
我们可以使用一个二维数组dp来存储中间结果。dp[i][j]表示在前i个商品中选择一些商品，使得总重量不超过j的最大价值。
状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中w[i]和v[i]分别表示第i个商品的重量和价值。
初始状态为：dp[0][j] = 0，表示没有商品时，总价值为0。
最终答案为：dp[n][W]，表示在前n个商品中选择一些商品，使得总重量不超过W的最大价值。
以下是用Go语言实现的代码：
package?main
import?(
"fmt"
)
func?knapsack(n?int,?W?int,?w?[]int,?v?[]int)?int?{
dp?:=?make([][]int,?n+1)
for?i?:=?range?dp?{
dp[i]?=?make([]int,?W+1)
}
for?i?:=?1;?i?<=?n;?i++?{
for?j?:=?1;?j?<=?W;?j++?{
if?w[i-1]?<=?j?{
dp[i][j]?=?max(dp[i-1][j],?dp[i-1][j-w[i-1]]+v[i-1])
}?else?{
dp[i][j]?=?dp[i-1][j]
}
}
}
return?dp[n][W]
}
func?max(a,?b?int)?int?{
if?a?>?b?{
return?a
}
return?b
}
func?main()?{
n?:=?4
W?:=?5
w?:=?[]int{2,?3,?4,?5}
v?:=?[]int{3,?4,?5,?6}
fmt.Println(knapsack(n,?W,?w,?v))?//?输出：7
}
这个算法的时间复杂度为O(nW)，满足题目要求。
在这里插入图片描述
在这里插入图片描述360智脑：
动态规划算法求解0-1背包问题的基本思路是：创建一个二维数组，其中行表示商品，列表示背包所能承受的最大重量。然后，从左上角开始，逐步填充数组，直到到达右下角。在填充过程中，对于每一个商品和每一个背包重量，我们有两种选择：包含当前商品和不包含当前商品。我们比较这两种选择中能够得到的最大价值，并将其存储在数组中。
下面是用Go语言实现的代码：
package?main
import?"fmt"
func?knapsack(weights?[]int,?values?[]int,?capacity?int)?int?{
n?:=?len(weights)
dp?:=?make([][capacity?+?1]int,?n?+?1)
for?i?:=?1;?i?<=?n;?i++?{
for?w?:=?1;?w?<=?capacity;?w++?{
if?weights[i-1]?>?w?{
dp[i][w]?=?dp[i-1][w]
}?else?{
dp[i][w]?=?max(dp[i-1][w],?dp[i-1][w-weights[i-1]]+values[i-1])
}
}
}
return?dp[n][capacity]
}
func?max(a,?b?int)?int?{
if?a?>?b?{
return?a
}
return?b
}
func?main()?{
weights?:=?[]int{1,?2,?3,?4}
values?:=?[]int{6,?10,?12,?16}
capacity?:=?5
fmt.Println(knapsack(weights,?values,?capacity))?//?输出：22
}
在这个代码中，我们首先定义了一个表示商品重量的切片weights，一个表示商品价值的切片values，以及背包所能承受的最大重量capacity。然后，我们创建了一个二维数组dp，其中dp[i][w]表示前i个商品中，价值最大的子集的总价值，且其总重量不超过w。
接下来，我们从左上角开始，逐步填充数组dp。对于每一个商品和每一个背包重量，我们有两种选择：包含当前商品和不包含当前商品。我们比较这两种选择中能够得到的最大价值，并将其存储在数组dp中。
最后，我们返回数组dp的右下角元素，即为所求解的0-1背包问题的最大价值。
在这里插入图片描述
在这里插入图片描述智谱清言：
0-1背包问题是一种典型的动态规划问题，其基本描述为：给定n种物品和一个容量为W的背包，物品i的重量是w[i]，其价值为v[i]，问应如何选择装入背包的物品，使得背包内物品的总价值最大，同时不超过背包的最大容量。
下面是使用Go语言实现的0-1背包问题的动态规划算法：
package?main
import?(
"fmt"
)
//?动态规划解0-1背包问题
func?knapsack(values?[]int,?weights?[]int,?W?int,?n?int)?int?{
//?dp[i][w]?表示考虑前i件物品，背包容量为w时能够装下的最大价值
dp?:=?make([][]int,?n+1)
for?i?:=?range?dp?{
dp[i]?=?make([]int,?W+1)
}
//?初始化dp数组，可以处理边界情况
for?i?:=?0;?i?<=?n;?i++?{
for?w?:=?0;?w?<=?W;?w++?{
if?i?==?0?||?w?==?0?{
dp[i][w]?=?0
}
}
}
//?填充dp数组
for?i?:=?1;?i?<=?n;?i++?{
for?w?:=?1;?w?<=?W;?w++?{
if?weights[i-1]?<=?w?{
//?可以选择放或者不放当前物品
dp[i][w]?=?max(dp[i-1][w],?dp[i-1][w-weights[i-1]]+values[i-1])
}?else?{
//?不能放当前物品，只能保持前i-1件物品的最大价值
dp[i][w]?=?dp[i-1][w]
}
}
}
//?返回最大价值，即装满背包时的最大价值
return?dp[n][W]
}
//?辅助函数，用于比较两个int类型的值
func?max(a,?b?int)?int?{
if?a?>?b?{
return?a
}
return?b
}
func?main()?{
//?示例数据
values?:=?[]int{60,?100,?120}
weights?:=?[]int{10,?20,?30}
W?:=?50
n?:=?len(values)
//?计算结果
maxValue?:=?knapsack(values,?weights,?W,?n)
fmt.Printf("The?maximum?value?is?%d\n",?maxValue)
}
这段代码构建了一个二维数组dp，其中dp[i][w]保存的是考虑前i个物品，并且背包最大容量为w时能够得到的最大价值。算法的时间复杂度为O(nW)，其中n是物品数量，W是背包的最大容量。这是因为我们需要填充一个n+1行W+1列的二维数组。每个元素的计算只依赖于它左上角的元素和它的上一个元素，因此没有嵌套循环，直接计算即可。
在这里插入图片描述
在这里插入图片描述在这里插入图片描述天工：
要设计一个运行时间为 O(nW) 的动态规划算法来解决 0-1 背包问题，我们可以使用一个一维数组dp来存储每个重量下的最大价值。这里的关键是要理解状态转移的过程，我们不是简单地遍历所有可能的重量组合，而是根据背包的剩余容量来更新dp数组。
以下是一个使用 Go 语言实现的 0-1 背包问题的动态规划解决方案：
package?main
import?"fmt"
//?0-1?Knapsack?Problem?solution?with?time?complexity?O(nW)
func?knapsack(W?int,?weights?[]int,?values?[]int)?int?{
if?len(weights)?==?0?||?W?==?0?{
return?0
}
dp?:=?make([]int,?W+1)?//?+1?to?include?the?case?where?no?items?are?taken
for?i?:=?1;?i?<=?len(weights);?i++?{
for?j?:=?1;?j?<=?W;?j++?{
if?weights[i-1]?<=?j?{
dp[j]?=?max(dp[j],?dp[j-weights[i-1]]+values[i-1])
}?else?{
dp[j]?=?dp[j]
}
}
}
return?dp[W]
}
//?max?returns?the?larger?of?two?integers
func?max(a,?b?int)?int?{
if?a?>=?b?{
return?a
}
return?b
}
func?main()?{
W?:=?5?//?Maximum?weight?that?can?be?put?in?the?backpack
weights?:=?[]int{1,?2,?3}?//?Weights?of?the?items
values?:=?[]int{6,?10,?12}?//?Values?of?the?items
result?:=?knapsack(W,?weights,?values)
fmt.Println("Maximum?value?that?can?be?obtained?is:",?result)
}
在这个实现中，我们首先检查是否至少有一个项目或背包容量不为零，如果没有，则返回零作为最大值。然后，初始化一个大小为W+1的dp数组，用于存储每个可能的重量下的最大价值。
接着，我们遍历每个项目，对于每个可能的背包重量，我们根据当前项目的重量来更新dp数组。如果当前项目的重量小于或等于背包的当前重量，我们就更新dp[j]为dp[j-weights[i-1]]+values[i-1]，否则保持dp[j]不变。
最后，dp[W]将包含背包能够容纳的最大价值。
注意这个算法的时间复杂度是 O(nW)，其中 n 是商品的数量，W 是背包的最大容量。这是因为我们需要对每个可能的背包重量和每个项目进行迭代。
在这里插入图片描述
在这里插入图片描述灵小智：
下面是使用 Go 语言实现动态规划算法求解 0-1 背包问题的代码：
package?main
import?"fmt"
func?knapsack(weights?[]int,?values?[]int,?W?int)?int?{
n?:=?len(weights)
dp?:=?make([][]int,?n+1)
for?i?:=?0;?i?<=?n;?i++?{
dp[i]?=?make([]int,?W+1)
}
for?i?:=?1;?i?<=?n;?i++?{
for?j?:=?1;?j?<=?W;?j++?{
if?weights[i-1]?>?j?{
dp[i][j]?=?dp[i-1][j]
}?else?{
dp[i][j]?=?max(dp[i-1][j],?dp[i-1][j-weights[i-1]]+values[i-1])
}
}
}
return?dp[n][W]
}
func?max(a,?b?int)?int?{
if?a?>?b?{
return?a
}
return?b
}
func?main()?{
weights?:=?[]int{2,?3,?4,?5}
values?:=?[]int{3,?4,?5,?6}
W?:=?8
maxValue?:=?knapsack(weights,?values,?W)
fmt.Println("背包中能获得的最大价值为:",?maxValue)
}
此代码通过动态规划的方式解决了 0-1 背包问题，其中weights列表存储每个商品的重量，values列表存储每个商品的价值，W是背包的最大重量。函数knapsack返回背包中能获得的最大价值。输出结果为背包中能获得的最大价值。
在这里插入图片描述
在这里插入图片描述chatgpt：
以下是使用Go语言编写的动态规划算法求解0-1背包问题，运行时间复杂度为O(nW)：
package?main
import?(
"fmt"
)
func?knapSack(W?int,?wt?[]int,?val?[]int,?n?int)?int?{
dp?:=?make([][]int,?n+1)
for?i?:=?0;?i?<=?n;?i++?{
dp[i]?=?make([]int,?W+1)
}
for?i?:=?0;?i?<=?n;?i++?{
for?w?:=?0;?w?<=?W;?w++?{
if?i?==?0?||?w?==?0?{
dp[i][w]?=?0
}?else?if?wt[i-1]?<=?w?{
dp[i][w]?=?max(val[i-1]+dp[i-1][w-wt[i-1]],?dp[i-1][w])
}?else?{
dp[i][w]?=?dp[i-1][w]
}
}
}
return?dp[n][W]
}
func?max(a,?b?int)?int?{
if?a?>?b?{
return?a
}
return?b
}
func?main()?{
val?:=?[]int{60,?100,?120}
wt?:=?[]int{10,?20,?30}
W?:=?50
n?:=?len(val)
maxValue?:=?knapSack(W,?wt,?val,?n)
fmt.Println("Maximum?value:",?maxValue)
}
上述代码中，knapSack函数接受参数W（背包容量）、wt（商品重量数组）、val（商品价值数组）和n（商品数量），返回背包能够装下的最大价值。max函数用于返回两个整数中的较大值。
在示例中，给定3个商品的重量（wt）和价值（val），背包容量为50。根据动态规划算法，计算并输出背包能够装下的最大价值为220。
请注意，这只是一个基本的0-1背包问题求解算法示例。实际应用时，请根据具体需求进行相应修改。
在这里插入图片描述
在这里插入图片描述kimi：
0-1 背包问题是一个经典的动态规划问题。在这个问题中，我们有n个商品，每个商品有一个重量w[i]和一个价值v[i]。我们的目标是选择一些商品放入一个最大容量为W的背包中，使得背包中商品的总价值最大。
动态规划算法使用一个二维数组dp[i][j]来存储前i个商品放入容量为j的背包时能够获得的最大价值。状态转移方程如下：
dp[i][j]?=?max(dp[i-1][j],?dp[i-1][j-w[i]]?+?v[i])?for?all?1?<=?i?<=?n?and?0?<=?j?<=?W
以下是使用 Go 语言实现的 0-1 背包问题的动态规划算法：
package?main
import?(
"fmt"
)
func?knapsack(W?int,?weights?[]int,?values?[]int)?int?{
n?:=?len(values)
dp?:=?make([][]int,?n+1)
for?i?:=?0;?i?<=?n;?i++?{
dp[i]?=?make([]int,?W+1)
}
for?i?:=?1;?i?<=?n;?i++?{
for?j?:=?0;?j?<=?W;?j++?{
if?j?>=?weights[i-1]?{
dp[i][j]?=?max(dp[i-1][j],?dp[i-1][j-weights[i-1]]+values[i-1])
}?else?{
dp[i][j]?=?dp[i-1][j]
}
}
}
return?dp[n][W]
}
func?max(a,?b?int)?int?{
if?a?>?b?{
return?a
}
return?b
}
func?main()?{
W?:=?50?//?小偷能放进背包的最大商品总重量
weights?:=?[]int{10,?20,?30}
values?:=?[]int{60,?100,?120}
maxValue?:=?knapsack(W,?weights,?values)
fmt.Printf("Maximum?value?that?can?be?put?in?the?knapsack:?%d\n",?maxValue)
}
在这个实现中，我们首先定义了一个knapsack函数来执行动态规划算法。我们初始化一个二维数组dp，并使用两层循环来填充它。对于每个商品i和每个背包容量j，我们根据状态转移方程来更新dp[i][j]的值。最后，我们返回dp[n][W]，即前n个商品放入容量为W的背包时能够获得的最大价值。
这个算法的时间复杂度是 O(nW)，因为它需要填充一个n+1xW+1的二维数组。其中n是商品的数量，W是背包的最大容量。
在这里插入图片描述
在这里插入图片描述混元：
以下是使用 Go 语言实现的 0-1 背包问题的动态规划算法：
package?main
import?(
"fmt"
)
func?knapsack(W?int,?weights?[]int,?values?[]int,?n?int)?int?{
//?初始化动态规划表
dp?:=?make([][]int,?n+1)
for?i?:=?range?dp?{
dp[i]?=?make([]int,?W+1)
}
//?动态规划求解
for?i?:=?1;?i?<=?n;?i++?{
for?w?:=?0;?w?<=?W;?w++?{
if?weights[i-1]?<=?w?{
dp[i][w]?=?max(dp[i-1][w],?dp[i-1][w-weights[i-1]]+values[i-1])
}?else?{
dp[i][w]?=?dp[i-1][w]
}
}
}
return?dp[n][W]
}
func?max(a,?b?int)?int?{
if?a?>?b?{
return?a
}
return?b
}
func?main()?{
W?:=?10
weights?:=?[]int{2,?3,?4,?5,?9}
values?:=?[]int{3,?4,?5,?8,?10}
n?:=?len(weights)
result?:=?knapsack(W,?weights,?values,?n)
fmt.Println("最大价值为：",?result)
}
这个算法的时间复杂度为 O(nW)，其中 n 为商品数量，W 为小偷能放进背包的最大商品总重量。
在这里插入图片描述
在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OrekV10f2JamANn9QQJpL2Ew0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
