浅谈DP算法(1) )。
——一维数组解决01背包问题的方法
DP算法(动态编程，俗称动态规划)是最典型的算法之一。 本笔记以大家熟悉的数塔问题为例，详细研究01背包的解决方法。
首先，如下图所示，要求从最上层到最下层。 如果每个步骤只能到达相邻节点，则通过的节点的数字之和最多是多少？
这个问题对于任何节点，直接选择数字大的子节点显然都是不可能的。 以9为例，选择15表示当前和2421，但15个子节点太小，为24 6 1821 10 18。 由此可见，这样求各阶段的部分最优解并不是全局最优解。 另外，在非力算法中，如果遍历各路径一次，则层数为n时
显然这种方法计算量太大，不理想。 在这种情况下，使用DP算法是有效的。 具体的想法是从倒数第二层开始，一层一层地向上扫描。 倒数第二层的第一个节点是2，当路径通过2时，一定会选择数值大的左子节点19。 用19 2=21代替原来的2。 同样地，18将改为18=28，9的5改为21。 这样，倒数第2段成为21281921的4个节点，舍弃最后一段。 这样向上到第1段，选择第2段较大的节点加在9上，就可以得到全局最优解。
代码实现：如果数字塔是n层，打开一个n*n二维数组即可。 虽然非常简单，但在此省略。
在对动态规划思想有了基本了解后，总结了动态规划的基本概念。 但是，在此之前，首先要说明什么是多阶段的决策问题，什么是状态。
多阶段决策问题：一个问题分为几个阶段，每个阶段都要做决策
状态：各阶段开始面临的自然状况或客观条件。 在上述例子中，选择每个阶段的状态到达当前节点的两个子节点。
动态规划在多阶段决策问题中，各阶段采取的决策依赖于当前状态，并引起状态的转变，一个决策序列产生于变化状态中，因此具有“动态”的意义，解决这种多阶段决策优化问题的方法称为动态规划方法。
应用DP算法的问题一般具有以下特点：
(1)最优化原理(最佳子结构的性质) ) ) ) ) ) ) )。
优化策略的子策略也是最好的。 举个例子可以清楚地看到，如数字塔问题，从第二层到最底层的数值和最大路径一定是从最上层到最底层的数值和最大路径的子集；
)2)无后向性(无后效性) ) ) )。
一般来说，如果确定了某个阶段状态，则不受该状态之后的决策的影响；
)3)子问题重叠
也就是说，子问题之间不独立。与前两个不同，这个特征不是必要的，如果不满足，DP算法就没有优势。如果独立，分割统治算法的策略就更简单方便。
看看经典的01背包问题：
如果在容量为v的背包中包含n个项目，则第I个项目所需的空间为need[i]，同时其价值为value[i]，该如何使背包中的项目达到最大价值？
分析：任何东西都只能选择装不装，所以叫做01背包。 在best(n，v )中，n个代表放入容量为v的背包的最大价值。 对于第n个，有两种选择：放入或不放入，除非是need[N]V。
)1)把第n个放在背包里
best(n，v )=best(n-1，V-need[N] ) value[N]； //，即等于第n个项目的价值加上将N-1个项目放入V-need[N]容量背包的最大价值。
)2)不放置时
best(n，v )=best(n-1，V-need[N] ) value[N]； //，即等于第n个项目的价值加上将N-1个项目放入V-need[N]容量背包的最大价值。
这样，如果重复上述步骤直到n和v减少到0，则对于任意一个物品I(1=I=n )，当前状态背包的剩馀容量为j ) j (0=j=V )
if(j )
best(I，j )=best ) I-1，j )；
else
best(I，j )=max best(I-1，j-need[i] ) value[i]，best (I-1，j ) }；
这是从第I阶段到第i-1阶段的状态转移规律，程序员为了提高追赶度，建立了——状态转移方程
另一方面，i=0时**只是设定边界值best[0，j]=0。 因此，如果解决best[n，v]这一复杂而棘手的问题，则从i=0时的best[0，j]=0变为i=N时的best[n，j]
*best(n，v )只是物品、背包容量和价值三者之间的关系表示。 请不要烦恼它为什么会这样显示，到底是什么意思，其中是如何基于n，v获得价值的。
i=0本来就没有意义。 因为它会从第n个物品引导到第一个物品。 设定i=0时的best(I，j )只是为了满足数学计算。
以下主题是经典DP算法背包问题的变种：
高个子蝴蝶今天很开心。 在家里买的新房要钥匙。 新房有他专用的宽敞房间。 更高兴的是，妈妈昨天告诉了他。 “你的房间需要买什么样的？ 怎么配置？ 你说
了算，只要不超过N元钱就行”。今天一早高大的小蝴蝶就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N元(可以等于N元)的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号)
请你帮助高大的小蝴蝶设计一个满足要求的购物单。
实现代码如下：
package huawei;
public class Demo {
/*
* 功能:
*
* 输入参数：a为二维数组，该二维数组第0行的两个数分别表示：总钱数<30000，和希望购买物品的个数<25;
* 该数组从第1行到第m行(1<=j<=m)中给出了编号为j的物品的基本数据，每行有2个非负整数，
* 表示该物品的价格(<=10000)和该物品的重要度(1~5)。
*
* GetResult表示不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。
*
* 不需做入参检查，测试用例可以保证～
*
* 例如：4000 8(第0行) 821 3 (第1行) 422 5 458 5 500 3 200 2 430 4 530 3 239 3
*
* 则表示 总钱数为4000，希望购买物品个数为8个，因此从第1行到第8行表示编号为j的物品的价格及物品的重要度。
*
*
*
*
* 返回值：无
*
* 温馨提示：根据题意可知，该二维数组只有两列，且行数为第0行的第二个元素数值+1;
*/
public int getResult(int[][] a) {
// 在这里实现功能
int money = a[0][0], numMax = a[0][1];
int[][] max = new int[a.length][money + 1];
for (int i = 1; i <= numMax; i++) {
for (int j = 1; j <= money; j++) {
if (j >= a[i][0]) {
max[i][j] = Math.max(max[i - 1][j], max[i - 1][j - a[i][0]] + a[i][0] * a[i][1]);
} else {
max[i][j] = max[i - 1][j];
}
}
}
return max[numMax][money];
}
}