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