前言
这是学习算法分析与设计过程中的一次作业，主要目的是讲清楚本次作业的问题和一些个人思考，对于为什么要这样设计动态规划的算法，本片文章没有过多说明。（要考虑四个步骤等等）
本人是一个学生，第一次发表文章（其实是自己写的作业），如果有不足还请见谅。（毕竟能力有限）
希望可以帮到大家
一、PPT上的作业一（解释01背包问题过程）：
题目简述：有个容量为22的包，装5个物品，求装入价值最大，典型的0-1背包问题。简单的算法是尝试各种可能的商品组合，并找出价值最高的组合。为了提高效率我们引入了备忘录，但是更好的做法（更优化的方法）是动态规划的常规做法：自底向上应用求解。
图表：每个动态规划算法都由一个网格开始，网格各行表示可选择的商品，各列为不同容量（1到22容量）的背包。分析和解动态规划问题一般分为4个步骤，01背包问题类似于电路布线问题，但是区别于应用贪心算法的部分背包问题。由于背包空间利用率的考虑，所以不能单单考虑性价比问题。本题主要问题是具体的求解过程，其过程由下图表示，该问题是属于动态规划中较简单的问题，因为对于每个小问题只需要考虑在与不在背包中，两种情况。在自底向上的表示中，表格中每个值，需要用到上方或左上方的值（由递推关系得出），有了表格间的关系，所以填写表格的顺序也就有了。
求解过程：第一行第一列为0。第一列：因为如果背包容量为0，里面无法装入物品，总价值为0；第一行：因为如果考虑的装入背包的物品范围为0到0，则说明没有物品可以装入，所以总价值为0。（其实在实现时初始化，表格的每个位置都为0），然后填表格，由于我们找到了表格见的关系，每个位置的填写表格的方式为：首先检查第i个物品能否放进背包（上课说的入场券），如果放不进，那只有一种情况，最大价格等于考虑物品范围在0到i-1时该容量下的最大价值（表格上方的值直接拉下来）。如果有入场券（能放进背包）就考虑是放进背包还是不放进背包两个情况，哪个情况的最大价值大，所以就像上表写的一样，比较如果装进去，背包装的物品价值为不装该物品背包剩余容量为当前容量减去当前物品的重量（本题时重量，也可以是体积）时的最大价值（子问题的最优解）加上当前物品的价格（左上角），如果装不进去，和没有入场券的情况类似，比较这两个值，大的为当前情况的最大价值。
解：当装入物品编号为2、4、5的物品时，背包里的价值最大，最大价值为25，此时背包剩余空间为0.
代码与时间复杂度：时间与空间复杂度为：O(nc)，下面为主要代码（还有辅助用的print代码等）
int const NumObj = 5; //Number of objects 物品个数
int const capacity = 22; //背包容量
int w[NumObj + 1] = { 0 , 3 , 5 , 7 ,8 ,9 }; //各商品的重量
int v[NumObj + 1] = { 0 , 4 , 6 , 7 , 9,10 }; //各商品的价值
int dp[NumObj+1][capacity+1] = { { 0 } }; //最优价值表、动态规划表
int item[6]; //存取最优解情况（也可以不用）
void optimalSolution() { //动态规划，填表，计算最优解
for (int i = 1; i <= NumObj; i++) { //对于每个物品，逐行填表，每次多考虑一个物品
for (int j = 1; j <= capacity; j++) { //容量范围逐渐增加，填表
if (j < w[i]) //判断是否有入场券
dp[i][j] = dp[i - 1][j];
else //有入场券后考虑两种情况，比较最优
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
void Construct(int i, int j) { //构造最优解（前面的图中有画该过程）
if (i >= 0) {
if (dp[i][j] == dp[i - 1][j]) { //跟 电路布线 类似 与上面的值比较
item[i] = 0; //0代表没有选这个物品
Construct(i - 1, j);
}
else if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) {
item[i] = 1; //1代表选了个物品
Construct(i - 1, j - w[i]);
}
}
}
二、书上的题p80 3-4（由于都是背包问题，故另一个PPT在后面讨论）：二维背包问题
思考：继续前面的思路，普通的背包问题只考虑了重量（如上题）或者体积，现在要同时考虑这两个因素。多了一个变量，那很自然要多个维度，之前是个平面的表格，现在多了一个变量变成了立体的表格。沿着上一题的思考，现在的入场券应该是质量和体积都满足放入背包的要求的情况，如果不满足该条件填表格时就填入不放人该物体剩这些容积和容量的情况。如果可以放入有了入场券则比较，一般使用p或者m代表最优价格，比较p（i-1，j，k）与p（i-1，j-wi，k-bi）+pi，其中j代表剩余的容量c（上一题的c），k代表剩余的容积，pi是当前的物品的价格。当然这只是很自然的推广，对错和细节还要认真考虑，如果这样填表，表格将是一个3维的，每一层代表考虑物体的范围，每一层的横纵坐标是剩余的容量和容积，那按照前面的式子，则当前问题的解是需要低一层的解，可能是正下方的值（从低向上填表），也可能是执行原点方向的一个值，所以每一层只要上一层的表格完成该层的表格就可以完成。下面我画了一张3维的彩色立体图来方便理解，但是由于打印是黑白的，不知道最终效果如何。
准确的说：参照上题，我创建了一个item数组存储最优情况，其中里面的值为0或者1，在构建最优解的时候如果值是0代表没选该物品，如果值是1则选了该物品，该题的问题用这个数组表示就是求：\mathbf{max}{\sum_{i=1}^{n}{x_i\timesv_i}},当然还有两个限制条件，限制条件就是总的容量与容积不超过范围，这样我们就得到了递归式：如果没有入场券，p（i，j，k） = p（i-1，j，k）使用p表示价值是为了和上一题保持一致，如果有入场券则p（i，j，k） = max{ p（i-1，j，k），p（i-1，j-wi，k-bi）+vi }，这两个式子就是描述的上面的内容，如此我尝试着在第一题的基础上更改代码完成这个题，动态规划的时间复杂度一般都很好分析，为O（ncd），n个物品，容量为c，容积为d。
int const NumObj = 5; //Number of objects 物品个数
int const capacity = 22; //背包容量（质量）
int w[NumObj + 1] = { 0 , 3 , 5 , 7 ,8 ,9 }; //各商品的重量
int v[NumObj + 1] = { 0 , 4 , 6 , 7 , 9,10 }; //各商品的价值
//新加：（瞎编的数，运行一下看看是否能求出最优）
int const volume = 25; //背包空间大小（体积）
int c[NumObj + 1] = { 0 , 4 , 4 , 9 ,10 ,16 }; //所占容积
//更改，加了一个维度
int dp[NumObj + 1][capacity + 1][volume + 1] = { {0} }; //最优价值表、动态规划表
int item[6]; //存取最优解情况（也可以不用）
void optimalSolution() { //动态规划，填表，计算最优解
for (int i = 1; i <= NumObj; i++) { //对于每个物品，逐行填表，每次多考虑一个物品
for (int j = 1; j <= capacity; j++) { //容量范围逐渐增加，填表
//多了一次循环，逻辑还是一样
for (int k = 1; k <= volume; k++) {
if (j < w[i] || k < c[i]) //判断是否有入场券，注意是或者
dp[i][j][k] = dp[i - 1][j][k]; //判断条件增加了一个，逻辑很简单
else //有入场券后考虑两种情况，比较最优
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - w[i]][k - c[i]] + v[i]);
}
}
}
}
void Construct(int i, int j,int k) { //构造最优解（前面的图中有画该过程）
if (i >= 0) {
//多了一个k,逻辑完全相同
if (dp[i][j][k] == dp[i - 1][j][k]) { //跟 电路布线 类似 与上面的值比较
item[i] = 0; //0代表没有选这个物品
Construct(i - 1, j,k);
}
else if (j - w[i] >= 0 && dp[i][j][k] == dp[i - 1][j - w[i]][k - c[i]] + v[i]) {
item[i] = 1; //1代表选了个物品
Construct(i - 1, j - w[i], k - c[i]);
}
}
}
该代码完全根据上一题的代码自主更改，最终算出来在该数据的情况下最大价值为22（选择物品2，3，4）为了使这个例子不选择物品5，稍稍调大了物品5的体积，数据是完全自主编造的。代码中与上题有所更改的地方均注释标注了出来，经过验证，该程序是可以完美的执行的。
该题经过了第一题的分析，其实非常简单，只要沿着思路推广即可。其实还有一个思路，就是构建一个结构体，那样的化或许更接近上一题的思路，也就可以看成二维的了吧，但是对于实现，但是这样的推广更容易更好理解。
三、 PPT上的作业二（写算法），硬币问题：
前述：这道题是要解最小硬币问题，与背包问题较为相似，但是又有区别。而且在做这道题的时候就一直在想，是不是也可以使用贪心算法，并在完成该作业后用贪心算法进行了尝试（贪心算法主要是证明其正确性，理解起来很简单）。本道题可以采用解动态规划的那几个步骤思考，动态规划就是找关系，如果找到网格间关系并且想通，则非常简单。能够快速找到动态规划的解最好的方法是不断的练习，遇到问题多自己思考。
其实该问题的最优子结构递推式很简单，就是每次增加一个硬币数量，可以是不同的硬币也可以是相同的硬币，所以我的代码里出现了外层的二重循环，其实就是每次多考虑一个数量。不断地更新表格（也可以是多维表格，每次填一行，是一样的），更新表格的值代表当前面额的钱可以用多少硬币凑出来，如果为无穷就说明不能用硬币凑出来。而最优子结构就是考虑要不要使用当前硬币，这里跟背包问题很像。下面先放代码，代码的每一行有我为什么这样写的解释，然后再来继续讨论。代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
//根据题意可以定义以下数据结构，命名均与题目对应
int m; //m代表要找的钱的数额
int n; //n代表拥有的硬币种类，比如有1元、2元、5元的三种硬币，由题意得，n最大为20001
int T[20001]; //T是存面值的数组，根据题目可知，面值最多可为20001种，如果每种面值只有1个硬币的话
int Coin[20001]; //用于存每个面值的硬币的对应个数
int const infinite = -1; //定义初始值为无穷，用-1表示无穷
long long int dp[20001] = {infinite}; //定义最优表格并初始化，所有位置均为无穷，也可以使用memset初始化函数
memset(dp, infinite, sizeof(dp));
//注：这里有个优化，本来应该是二维表格，为了节省空间，使用了一维表不断的在一行求值，遇到更优就覆盖
//定义用于测试的一组数据，也可以使用cin输入，使用了常见的5种硬币
n = 5;
T[0] = 1; Coin[0] = 3;
T[1] = 2; Coin[1] = 3;
T[2] = 5; Coin[2] = 3;
T[3] = 10; Coin[3] = 5;
T[4] = 20; Coin[4] = 1;
m = 48;
//最优是使用一张20，两张10，一张5，一张2，一张1，6个硬币，此程序可以正确求出来
dp[0] = 0; //初始情况是使用0个硬币
//填表求值，这里要注意边界等号
for (int i = 0; i < n; i++) //对于每个面值的硬币
for (int j = 1; j <= Coin[i]; j++) //面值硬币的数量
for (int k = m; k >= T[i]; k--) //要找的钱的数额，初始是m,当比当前硬币面值大的时候循环，每次钱的数额-1；
//当最优不是无穷的时候（即有值，即可以使用硬币找钱m），并且如果使用当前面值硬币的时候，要凑k - 当前面额可以凑出来的时候
if (dp[k] != infinite && dp[k - T[i]] != infinite)
//注意这里的理解，比较，用子问题求最优，为了优化使用了一维数组，因为题目只要求个数，如果可以凑出来m和m减当前面值
//求哪一种情况用到的硬币少，当然第二层循环是硬币的数量，这是因为当j = 1时求了一遍，更新了表格，注意是每个位置都有更新
//当有两个一样的硬币时，第二次更新是在第一次的基础上，比如20的面额，第一次更新，qp【10】 = 1，第二次更新表格dp【20】才等于2
// 简单说就是每次增加一个硬币数量
//将在作业中更详细的讨论细节，以上只是简单的理解
dp[k] = min(dp[k], dp[k - T[i]] + 1);
else if (dp[k - T[i]] != infinite)
dp[k] = dp[k - T[i]] + 1;
//判断是否找到最优解,第二种写法更人性
//cout << (dp[m] != infinite ? dp[m] : -1) << endl;
if (dp[m] != infinite)
cout << "需要的硬币数量为：" << dp[m] << endl;
else
cout << "无法使用当前的硬币凑出数额m" << endl;
}
代码：因为代码是完全自己写的，所以每一行我都写出了为什么这样写，和一些思考，里面用到的符号均与题目对应，dp一般用于表示最优值表格，这里沿用这样的命名习惯也使用dp。看完代码再结合前面的一小段解释，会明白我的思路，这个思路完全和背包问题类似，考虑的情况也只有使用还是不使用当前硬币，时间复杂度也很容易分析，时间复杂度为O(num×m)，num为硬币数量，大小为ni乘以Coin i的累加（自己分析的，应该没有问题）。继续前面的讨论，每次都更新一次表格，第一次更新只是一种硬币只有一个，当然只能凑出dp[硬币面额]这个值，然后再更新，如果能凑出来一个面额k而以前不能凑出来，就是else if的情况，那直接填入表格，如果以前也能凑出来这个面额k，现在也可以凑出来，则比较，看哪个情况用的硬币少。如果都凑不出来则还是保存需要无穷个硬币。如果换成二维数组，那每行代表一个硬币数量，比如说有15行（代码中的例子，例子是自己编的）每行为1，1，1，2，2，2，5，5，5，10，10，10，10，10，20这些值，而每列表示要凑的硬币面额，而最后如果要构造最优解也将与背包问题相同。最后一行或者说这里的dp数组最终存的值为，要凑的一个面额（从0到m），需要的硬币数，当然如果值为infinite则为无解，如果我也要求m-1，我可以直接在最后输出dp[m-1]，而不需要动其他地方。
关于贪心算法：当然本题使用贪心算法也可以求解，而且更简单，但是使用贪心算法就要证明解的正确性，具体马上就会学到，因为提前看到了贪心，故给出贪心算法的代码（很容易理解）。
一些思考：在最后我一直在思考：如果01背包问题中每个物品不止一件？如果背包必须装满？如果硬币问题最后凑出对应的使用的硬币数，数量少则其更有意义，用价值描述就是数量少代表其价值大，如果这样考虑？如果硬币问题改为使用最少的硬币凑出小于m而且最接近m的值时最少的硬币数？如果不同面额的硬币有不同的重量，要求最终凑的总重量小于一个值？等等，如果考虑这些如果，那么这次的这三个问题就是一个问题，因为背包必须装满，空间得以完全利用所以使用贪心策略是正确的（需证明），而硬币问题不就是背包必须装满的情况吗？当然在这次的实验中，我有很多这样的思考，或许因为动态规划问题都满足那两个特点故总会有些相似吧。这些思考只是在解这些问题时的灵光一闪，但是却让我沉思了很久，我认为这些思考是有意义的，并且认为这次的问题并没有本质的不同。（不像最少编辑问题和最长公共子序列问题，虽然递推式相似，但是思考的本质是不同的）
作业总结：本次作业是在完成对应的实验报告之后完成的，此时再自己尝试完成这些题就有了很多的底气。在完成作业的时候我尽可能自己思考，并且努力讲清楚（因为真正的掌握是需要讲出来的，讲是很重要的）。在努力讲清楚的同时，我尽可能的避免写过多的内容，当然由于是初学，肯定还有很多很多不完美的地方。这次的作业，在实验之后又一次很好的巩固了我对动态规划的理解，我相信如果未来我需要使用动态规划解决问题或者遇到使用动态规划问题的时，我可以应对它们。我一直在努力的更好的学习算法，但是总是感觉自己还差的很远，希望有一天可以真正掌握算法吧。