用动态规划解决问题:零壹背包问题(0/1 Knapsack Problem)
一个背着背包的小偷闯空门偷东西,他必须趁屋主回来之前把有价值的物品塞进包包内带走。考虑到小偷自身的行动力,背包能装的物品总重量有限,小偷要如何选择物品才能获得最高的总价值?
MagicLen · https://magiclen.org
本站也提供繁體中文版。切換到繁體中文版
标签
动态规划的观念与实战,先说明它适合处理哪些有重叠子问题的情境,再以 0/1 背包与找零钱为例,示范如何创建状态表并写出多种编程语言的解法。
共 3 篇文章
一个背着背包的小偷闯空门偷东西,他必须趁屋主回来之前把有价值的物品塞进包包内带走。考虑到小偷自身的行动力,背包能装的物品总重量有限,小偷要如何选择物品才能获得最高的总价值?
许多人认为身上如果带太多的零钱会让行动变得不方便,因此会希望商店店员在找零钱的时候能够以最少的硬币数来找,而不是全部都用 1 元塞给我们。
动态规划(Dynamic Programming,简称 DP)是一种解决问题的技巧,主要被用来优化那些「记不住自己过去曾解出来的答案所以只好重复再解」的算法,让它们可以「记忆」已经找出来的答案,从而不断利用,以大大降低时间复杂度(从指数级降到线性)。