[TOC]
根据维基百科，背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。一般来讲，背包问题有以下几种分类：
-
01背包问题
-
完全背包问题
-
多重背包问题
本问题是一个典型的01背包问题
最基本的背包问题就是01背包问题（01 knapsack problem）：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
假设有n件物品，这些物品的重量分别是W1 , W2 , … , Wn，物品的价值分别是V1，V2， …，Vn。求从这n件物品中选取一部分物品的方案，使得所选中的物品的总重量不超过限定的重量W（W<∑Wi, i=1,2,┅,n），但所选中的物品价值之和为最大。
功能划分：
使用技术：类和继承，多态技术，查询技术，文件流技术、交互技术等
技术：动态规划，迭代，回溯，动态数组
如果采用暴力穷举的方式，每件物品都存在装入和不装入两种情况，所以总的时间复杂度是O(2^N)，这是不可接受的。而使用动态规划可以将复杂度降至O(NW)。我们的目标是书包内物品的总价值，而变量是物品和书包的限重，所以我们可定义状态dp: $$ dp[i][j]是在装载重量为j，装载i件物品的情况 $$
所以，通过递归迭代的方式，我们可以考虑上一步的情况，即i-1步： $$ dp[i][j]=dp[i-1][j] \qquad \qquad \qquad \qquad j<w[i]\ \
max(dp[i][j]=dp[i-1][j] , dp[i][j]=dp[i-1][j-w[i]]+v[i]) \qquad \qquad else\ $$ 第一种情况即为第i个物品的的大小超过背包大小，此时只需要回溯上一种方案即可，
第二种情况是可以装下的的情况，又分为两种状态：a.维持上一个，因为加入了以后，并不会对增大价值，b.加入第i个，因为是从第i-1加到第i个，所以还是从第i个出发。
观察dp的数据结构，发现dp是一个二维可列数组，因此可以将结果抽象成一个表格，在这个表格中，将所有符合情况的i-j対应的v画了出来，故表上数值最大的值即为最优解
那么此时问题来了，我们只知道了最优解是什么，但是，如何确定此时背包的组成，此时我们就要用回溯法
我们可以理解，找到最大值的过程进行逆运算的话，我们可以把组成最优值的解集给完全解出来。
如果dp[i][j]=dp[i-1][j]:说明这一轮和上一轮没有区别，直接等效。该物品数量记为0
如果dp[i][j]=dp[i-1][j-w[i]]+v[i]:说明在这个过程中确实添加了物品，那就记为1.下一个就转移到dp[i-1][j-w[i]]
以上可以通过while循环或者递归来实现，边界条件为i>0
因为要扩大数组的范围，所以用new来开辟堆区，函数结束前，要用delete[]释放。
1模型抽象->数据结构设计
作为一个具有两种属性的数据结构，建议通过结构体（Item）的的方式存储数据，两种属性分别为重量（weight），价值（value），结构体的标号也可以作为物体的标号，注：可以设置骑兵点，即可以作为数据的单位元来使用，两个属性值均为0.物品集可以使用结构体数组数组（pitem）来储存，其大小是物品数+1（因为还要储存一个骑兵点）
动态规划表可以用二维数组去建立规模为*(item_num+1)**(bagV+1)*可以遍历所有情况
2.确定递归关系->核心算法
通过循环的方式进行递归，主要算法就是以上两个式子，可以遍历不同重量下的最佳组合
3.回溯->找到最优解空间
可以考虑函数迭代或者是while循环，将结果储存在数组之中
void init(int, int, Item*):
输入物品价值和重量
void core_algorithm1(int, int, Item*, int**):
递归计算动态规划表
void printtable(int item_num, int bag_size, int** ptable, int*):
打印动态规划表，并获取最优值
void findwhat(int& a, int** ptable, int& b, int* resultlist, Item* pitem):
根据最优值，反推出解集
详细设计：主要算法的框架、流程图，主要函数接口、成员函数接口等。
实现此算法的成员函数接口。
设计表示：类名及其作用，类中数据成员名称及作用，类中成员函数原型及其功能，或者是函数的原型及功能，可以用表格形式表达。
1.结构体
struct Item
{
int value = 0;
int weight = 0;
};//创建物品类2.函数
（1）初始化
void init(int bag_size, int item_num, Item* pitem)
{
//创建一个背包类,需要多创建一个位置以存储骑兵点（0,0）
//pitem[0] = { 0 };
for (size_t i = 1; i < item_num + 1; i++)
{
cout << "请输入第" << i << "个物品的价值：" << endl;
cin >> pitem[i].value;
cout << "并输入它的重量：" << endl;
cin >> pitem[i].weight;//输入基本属性
}
//pitem = NULL;
}接口：
init(bag_size, item_num, pitem);（2）核心算法
void core_algorithm1(int item_num, int bag_size, Item* pitem, int** ptable)
{
for (size_t i = 0; i < item_num + 1; i++)
{
for (size_t j = 0; j < bag_size + 1; j++)
{
ptable[i][j] = 0;
}
}
//向前迭代：分以下几种情况
//1.装不下第i个物品，复读上一个价值
//2.能装第i个物品，有两种情况
//a.装但是没必要，所以复读第个
//b.装第i个，所以在第i-1个加第i个
for (size_t i = 1; i < item_num + 1; i++)
{
for (size_t j = 1; j < bag_size + 1; j++)
{
if (j < pitem[i].weight)
{
ptable[i][j] = ptable[i - 1][j];
}
else
{
ptable[i][j] = max(ptable[i - 1][j], ptable[i - 1][j - pitem[i].weight] + pitem[i].value);//
}
}
}
//ptable = NULL;
}接口：
core_algorithm1(item_num, bag_size, pitem, ptable);//生成规划表（3）输出动态分配表
void printtable(int item_num, int bag_size, int** ptable, int* r)
{
cout << "动态规划表为: " << endl;
for (int i = 0; i < item_num + 1; i++)
{
for (int j = 0; j < bag_size + 1; j++)
{
cout << setw(2) << ptable[i][j] << " ";
if (ptable[i][j] >= max_result[2])//寻找最优结果
{
max_result[0] = i;
max_result[1] = j;
max_result[2] = ptable[i][j];
}
}
cout << endl;
}
}接口：
printtable(item_num, bag_size, ptable, resultlist);//打印规划表（4）回溯算法
void findwhat(int& a, int** ptable, int& b, int* resultlist, Item* pitem)
{
while (a > 0)
{
if (ptable[a][b] == ptable[a - 1][b])
{
cout << "a: " << a << "b: " << b << endl;
resultlist[a] = 0;
a = a - 1;
}
else if ((b - pitem[a].weight >= 0) && (ptable[a][b] == ptable[a - 1][b - pitem[a].weight] + pitem[a].value))
{
cout << "a: " << a << " b: " << b << endl;
resultlist[a] = 1;
b = b - pitem[a].weight;
a = a - 1;
}
}
}接口：
findwhat(a, ptable, b, resultlist, pitem);//回溯找到最优解3.数组
（1）最大值向量：
int max_result[3] = { 0,0,0 };//储存三元组的最大值通过printable循环比较可得：
if (ptable[i][j] >= max_result[2])//寻找最优结果
{
max_result[0] = i;
max_result[1] = j;
max_result[2] = ptable[i][j];
}（2）类（物品）数组
int bag_size, item_num;
cout << "输入背包大小：";
cin >> bag_size;
cout << "输入物品数量：";
cin >> item_num;
Item* pitem = new Item[item_num + 1];//创建物品表释放：
delete[]pitem;（3）动态表——二维数组
int** ptable = new int* [item_num + 1];
for (size_t i = 0; i < item_num + 1; i++)
{
ptable[i] = new int[bag_size + 1];
}//创建规划表释放：
for (size_t i = 0; i < item_num + 1; i++)//释放内存
{
delete[]ptable[i];
}（4）结果数组：
int* resultlist = new int[item_num + 1];释放：
delete[]resultlist;1.验证目前较为广泛的数据集-四阶：
数据集见附录
测试集可用“44背包问题.cpp”去测试
格式为：
bag_size item_num
第一个物体重量 第一个物体价值
……
……
……
第bag_size个物体重量 第bag_Size个物体价值
测试结果可以和总价格比较，因为网上大多的数据集都是只显示最大价格的，物品组成只能用自己去验算了
.png)
.png)
.png)
.png)
.png)
.png)
1.本算法将复杂度从O(2^n)降至O(Nw)大大提高了运算效率，减少了运算时间。
2.通过动态数组，提高了程序的定制性，可以让用户设定自己所需要的数据范围大小
3.中文步步指导，提高了界面的友好程度
4.个人方面，学习到了优化算法的基本知识，学会了如何去评估一个算法的优劣，了解到动态问题的基本解决方案，学会了从多方面去考虑问题，既要考虑到对用户的友好性，以及对与测试人员的方便性。
5.上手vs2022使用了许多非常方便的功能，比如快速提取函数，快速简化主函数界面，用codemaid整理代码，增加其易读性
6.增加窗口和重复输入，能够以一个体面的方式退出
本人并未找到更好的方法去优化算法的整体性能，在对于用户的意外输入方面，并没有做太多的准备，只能任由程序去遇到错误返回。
在回溯时，因为频频遇到内存冲突，于是放弃了使用递归法，而是用了循环法，这无疑会增加程序的负担。
1.解决问题之前一定要理解核心的算法，理解其数学原理
2.csdn烂了！！！我觉得有时还不如知乎，但是还能看看
3.学无止境，算法这一块这能算是刚刚入门