2023-09-16 15:50 门头沟学院 算法工程师
关注
背包问题求助
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]。
基础解决方法是二维状态数组，然后有个优化空间的解决办法——用一维状态数组。
不懂的地方是为什么双重循环里第二个要倒序
网上看到两种解释：
1. 正序枚举A[i]，并倒叙枚举j，这样所需要的dp[j-A[i]]不会被提前更新
2，因为新的结果要与其在二维素组中左上位置的元素比较（即一维数组中左边的元素比较），所以从后向前遍历一维数组
但是都看不太懂，有没有好心人愿意探讨一下
#晒一晒我的offer##现在还是0offer，延毕还是备考##0offer是寒冬太冷还是我太菜#（引流）
基础解决方法是二维状态数组，然后有个优化空间的解决办法——用一维状态数组。
不懂的地方是为什么双重循环里第二个要倒序
网上看到两种解释：
1. 正序枚举A[i]，并倒叙枚举j，这样所需要的dp[j-A[i]]不会被提前更新
2，因为新的结果要与其在二维素组中左上位置的元素比较（即一维数组中左边的元素比较），所以从后向前遍历一维数组
但是都看不太懂，有没有好心人愿意探讨一下
#晒一晒我的offer##现在还是0offer，延毕还是备考##0offer是寒冬太冷还是我太菜#（引流）全部评论
offer多多的咸鱼很糊涂
美团_算法策略
因为如果用一维背包且正序遍历，考虑把当前的物体放进背包时需要j-A【i】的状态，而这个状态如果是正序遍历就是已经被计算过了（即已经考虑要不要把当前物体放进背包了），这样就相当于一个物体可以被多次选择了，变成了完全背包问题。所以对于01背包一维dp需要倒序遍历
相关推荐
途游游戏
| 校招
| 超多精选岗位
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
01-16 15:40
点赞 评论 收藏
分享