基础知识：

关于动态规划的知识，请自行查看其他资料。这里不讲解何为动态规划，主要聚焦于实现。

因为很多资料讲的知识很多，但是没有示例。

小规模动态规划

所谓小规模，就是可以在允许的范围内利用二维表解决问题。二维表的大小取决于规划内容的数量以及最大允许范围。

就背包问题而言，取决于物品的件数和背包容量。

对于大规模的的问题，二维表的使用将会超出内存允许界限，这是将使用优化的数据结构，而不是一个不断增长或固定的数据结构。

 

具体实例：

数据结构：

//价值和体积数组，一一对应 vector<int> p, v; //动态规划表 vector<vector<int>> Csheet; //选中的物品序列，0为放弃，1为选中 vector<char> SelectedList;

核心代码：

//临时数组，规划表 vector<int > Cline; //vector<vector<int > > Csheet; //初始化，第0行填充 for (int i = 0; i <= c; ++i) { Cline.push_back(0); } Csheet.push_back(Cline); Cline.clear(); //动态规划 for (unsigned int i = 0; i < p.size(); ++i) { for (unsigned int j = 0; j <= c; ++j) { if (v[i] > j) { Cline.push_back(Csheet[i][j]); } else { Cline.push_back(Maxint(Csheet[i][j - v[i]] + p[i], Csheet[i][j])); } } Csheet.push_back(Cline); Cline.clear(); }

运行示例：

最后说明：

如果小伙伴需要源码的，请到我主页的资源里找dynamicprogramcpy.rar