【背包】
今天来讲讲背包问题
背包问题是DP问题的一种。
而DP问题离不开三个特性：
- 最优子结构
- 无后效性
- 重叠子问题
在讲背包问题之前，我们先讲讲斐波那契数列。
总所周知斐波那契数列的递推公式是
F(n)=F(n-1)+F(n-2)
但是我们可以画个图看看，在使用递归求解斐波那契数列第N项的时候会发生什么问题
写到这里应该就很清楚了。我们要求F（n）一定要递归求得F（n-1）和F（n-2），但是我们在求F（n-1）的时候，我还需要再递归求一个F（n-2），那么时间的开销就变大了许多许多。这就是上面DP说的重叠子问题，我重复地求了一个值，以至于当n很大很大地时候接近叶子节点地上一层地数据被计算了相当多次，这时间地开销是非常非常大的。而且我们从时间复杂度的角度出发，这个算法本身也是O(2^n)。
那么。我们从节省时间的角度我们去解决一下斐波那契数列。既然我们重复地计算了某一个值，那我们能不能用一个变量先存放他在那。直到用的时候，我才把他调度出来。也就是说，我们从n=2开始我们用for循环递进的方式，一个一个地求出前n-1项地值，那么我们在计算第n项地值得时候，我们就可以之间从数组中通过下标索引得方式去得到F（n-1）和F（n-2）从而计算出F（n）的值。
这里我就不进行代码实现了。
我们回归到今天的主角：背包问题
有N件物品和一个容量为V的背包。每种物品均只有一件。 第i件物品的质量是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的质量总和不超过背包容量，且价值总和最大。
在本题中，乍一看，好像没有思路，或者有的同学会觉得性价比方案可以解决背包问题
我们一步步来仿照刚刚的斐波那契数列的O（n）求解法
第一步
我们先完成简单的输入，把缓冲区的数据全部读进一个数组中，并按照价值，升序排序
struct object {
int val;
int weight;
};
//这里是存储的数据类型
int main() {
int T;
//T代表着我有多少个物体
while (cin >> T) {
int weight = 0;
cin >> weight;
object* Arr = new object[T];
for (int count = 0; count < T; count++) cin >> Arr[count].val >> Arr[count].weight;
//input
//sort
for (int count = 0; count < T; count++) {
for (int j = count+1; j < T; j++) {
if (Arr[count].val > Arr[j].val) {
//change
object tem = Arr[count];
Arr[count] = Arr[j];
Arr[j] = tem;
}
}
}
}
}
这里用了冒泡排序增强可读性，我们也可以用其他更快速的排序去减少时间的复杂度，不过这不属于我们的核心代码块
我们这里直接定义一个函数名为DP_bag
图解如下
于是我们便有递归实现的代码
int DP_bag(object *Arr,int Value,int weight,int last){
if (last < 0)return 0;//装不下了
else if (weight < Arr[last].weight)return DP_bag(Arr, Value, weight, last - 1);//装不下最贵的，往后找
else return max(DP_bag(Arr, Value, weight, last - 1), Arr[last].val +DP_bag(Arr, Arr[last].val + Value, weight - Arr[last].weight, last - 1));
}
找到最优子结构和重叠子问题后就可转换
我们先设置一个Dp数组，为了避免多次计算重叠的子问题，我们可以用一个DP数组来存储每一个值
int DP_bag(object* Arr, int T,int weight) {
int* DP = new int[weight+1];
memset(DP, 0, weight+1);//T3RSCG
for (int i = 0; i < T; i++) {
for (int j = weight; j >= Arr[i].weight; j--) {
DP[j] = max(DP[j], DP[j - Arr[i].weight] + Arr[i].val);
}
}
return DP[weight];
}
我们来解剖一下这段代码，在DP数组中，J表示的是目前的程重，而第一层循环遍历了所有的物体，第二次循环则是根据每次物体的属性更新他的值。因此我们只需要返回当程重等于给定程重时候的最大价值即可
上一段的解释有点粗糙，可能会让一部分的同学看不懂这段代码，但是暂时只能先写到这里，以后有更好的理解再进行修改（因为我太菜了）
总结一下把，该类的背包问题其实是属于01背包问题
在以二进制为主导数制的计算机中，0往往代表着低电平，1代表着高电平。
回归到该问题，我们无非离不开判断（放/不放），也就是1 与 0之间的关系。
01背包问题，也就因此得名
