背包九讲实例：01背包问题
date
Jul 30, 2023
slug
backpack-dp
status
Published
tags
算法
summary
dp经典题，背包九讲的实例
type
Post
背包九讲：背包九讲pdf
《背包九讲》没有实例好难李姐啊，所以找了实例🌰与大家分享。
问题
你的背包承重为 Capacity, 现在有n个物品，物品重量 w[n], 物品价值 v[n]。如何选择物品价值最大？
特点：每种物品仅有一件，可以选择放或不放, 即01.
实例输入：背包承重量10，5件物品，重量[2,3,3,4,6], 价值[1,2,5,9,4].
动态规划表格
表格说明
- 第一行： 表示最大允许重量 0 ～ 10。
- 比如7那一列 表示我们将背包的最大承重量当作7来求解。
- 第一列： 表示物品的 重量（价值）。
- 比如第四行 3（5）： 我们只考虑物品集合{ 2(1)，3(2)，3(5)}，剩下的 4（9），6（4） 当做不存在。
- 表格中具体某一个数，表示当前行列条件下能获取的最大价值。
- 比如第五行=4（9）第八列=6， 意味着当背包最大承重量为6，从 2（1），3（2），3（5），4（9）中挑选物品可以获取的最大价值，即10.
如何生成表格
比如最大承重量为5，第三行只考虑2（1），3（2）的情况：
- 如果不拿3（2）， 那么获取的价值可以从上一行得到，即只有2（1）的情况，结果为1.
- 如果拿3（2），那么获取的价值为 2 + 最大承重量为(5-3)=2的时候拿除了3（2）的物品能获得的最大价值，这个数值能从上一行最大承重2的那列获取，结果为3.
综上，应该拿3（2），最大价值为3.
总结
第i行，j列的数值应该等于：
max (dp\[i-1][j], v[i]+ dp\[i-1][j-w[i]])