经典动态规划：0-1 背包问题

点击上方蓝字设为星标东哥带你手把手撕力扣~作者：labuladong  公众号：labuladong若已授权白名单也必须保留以上来源信息后台天天有人问背包问题，这个问题其实不难啊，如果我们号动态规划系列的十几篇文章你都看过，借助框架，遇到背包问题可以说是手到擒来好吧。无非就是状态 + 选择，也没啥特别之处嘛。今天就来说一下背包问题吧，就讨论最常说的 0-1 背包问题，简单描述一下吧：给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？举个简单的例子，输入如下：N = 3, W = 4wt = [2, 1, 3]val = [4, 2, 3]算法返回 6，选择前两件物品装进背包 ………………………………