01背包问题详解
最终的答案就是13。
1.4如何构建表格？
使用公式dp[i][w] = max(dp[i-1][w], dp[i-1][w-重量[i]] + 价值[i])将表格填完整，所有格子默认为0
1.5为什么这样做？
问题可以拆碎
原问题是"n个物品装容量小于上线的物品"，我们把它拆成"前1个装各种容量"、“前2个装各种容量”……每个小问题独立求解。小问题的答案能复用
算第i行时，直接抄上一行的结果就行。因为"前i个"的最优解，要么包含第i个，要么不包含——不包含时就和"前i-1个"完全一样。选第i个时，剩下的仍是已解决的子问题
如果决定要第i个，那就先腾出它的重量，剩下的容量去装前i-1个——这个子问题上一行已经算过了，直接查表取数加价值即可。每个格子只存最优值
表格不记录"选了哪些物品"，只记录"最大价值是多少"。因为后续推导只需要这个数字，不需要具体组合。
1.6.1例题
P1048 [NOIP 2005 普及组] 采药
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有
个整数
（
）和
（
），用一个空格隔开，
代表总共能够用来采药的时间，
代表山洞里的草药的数目。
接下来的
行每行包括两个在
到
之间（包括
和
）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
输入输出样例 #1
输入 #1
70 3
71 100
69 1
1 2
输出 #1
3
说明/提示
【数据范围】
对于
的数据，
；
对于全部的数据，
。
【题目来源】
NOIP 2005 普及组第三题
1.6.2解法
本题每种草药只有选和不选两种选择，所以是01背包
1.6.3样例分析
70 3
71 100
69 1
1 2
总时间，共株草药
草药：耗时，价值采不了（）
草药：耗时，价值
草药：耗时，价值
最优方案：
采草药草药耗时
，价值
1.6.4代码详解