动态规划之背包问题

GitHub undefined undefined undefined

培养框架思维,真正爱上算法!关注公众号查看更新文章👆

相关推荐:


本文有视频版:0-1背包问题详解

后台天天有人问背包问题,这个问题其实不难啊,如果我们号动态规划系列的十几篇文章你都看过,借助框架,遇到背包问题可以说是手到擒来好吧。无非就是状态 + 选择,也没啥特别之处嘛。

今天就来说一下背包问题吧,就讨论最常说的 0-1 背包问题。描述:

给你一个可装载重量为 W 的背包和 N 个物品,每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i],价值为 val[i],现在让你用这个背包装物品,最多能装的价值是多少?

举个简单的例子,输入如下:

N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]

算法返回 6,选择前两件物品装进背包,总重量 3 小于 W,可以获得最大价值 6。

题目就是这么简单,一个典型的动态规划问题。这个题目中的物品不可以分割,要么装进包里,要么不装,不能说切成两块装一半。这就是 0-1 背包这个名词的来历。

解决这个问题没有什么排序之类巧妙的方法,只能穷举所有可能,根据我们「动态规划详解」中的套路,直接走流程就行了。

_____________

本文只能在 labuladong 公众号查看,关注后可直接搜索本站内容:

Copyright © labuladong 2020 all right reserved,powered by Gitbook该文件修订时间: 2021-04-19 18:19:23

results matching ""

    No results matching ""