传送门： 01背包问题（动态规划C++）
传送门 ：01背包问题
01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。
求解这个背包能装的最大价值。（物体不能分割）。
通俗点讲就是： 背包问题，可以理解为你的预算有限（背包的体积有限），要在预算的范围内买那些价值高（什么是价值高，就是你觉得目前来说非常需要的东西，通常用权重来衡量它）的东西。
这招可以用来清空购物车。。。
注：这招适用于所有物品都可得到，通过一个类似松弛函数进行局部优化，从而得到当前条件下的一个最优解。
为什么状态转移函数看着和斐波那契数列似的~v_i 表示第i个物品的体积，w_i表示第i个物品的价值。
这个问题让我想起了Dijkstra最短路径算法中的松弛函数。这里我们以背包容积为10，有5个物品为例。
体积43527价值96141先放第一个物品（体积为4），表格中表示（当前价值）。 实际上就是拿着当前的物品，从后向前以此松弛（更新）当前结果，即得解。
剩余容积012345678910第1个物品（体积4）00009999999第2个物品（体积3）000699915151515第3个物品（体积5）000699915151515第4个物品（体积2）00469101315151919第5个物品（体积7）00469101315151919查找00469101315151919通过倒着查找weight数组，判断是否可以放入该石头，就可得出装在包里的物品编号。 e.g. 19 （通过去除冗余最后一个下标得到）是第4个物品，15是第2个物品，9是第1个物品。
Talk is cheap, show you the code.
#include <iostream> #include <iomanip> using namespace std; int main(int argc, const char * argv[]) { //初始化 int volumeOfBackpack = 10;//定义包的体积 int numberOfStone = 5;//定义石头数量 int weight[volumeOfBackpack+1] = {0};//权重数组 int stoneVolume[numberOfStone] = {4,3,5,2,7}; int stoneWeight[numberOfStone] = {9,6,1,4,1}; //当前遇到的石头 int currentVolume = -1; int currentWeight = -1; // 01 背包问题 for (int i = 0; i < numberOfStone; i++) { currentVolume = stoneVolume[i]; currentWeight = stoneWeight[i]; for (int j = volumeOfBackpack; j > 0; --j) { //j是背包容量，weight[j]是原来的价值 weight[j-currentVolume]表示是（放进当前石头的体积）的价值 if (j >= currentVolume && weight[j] < weight[j-currentVolume] + currentWeight) { weight[j] = weight[j-currentVolume] + currentWeight; } //如果放不下当前石头 就跳出循环 if(j<currentVolume) { break; } } for (int j = 0; j <= volumeOfBackpack; ++j) { //每放一个石头就输出一下权重数组 cout<<setw(4)<<setiosflags(ios::left)<<weight[j]; } cout<<endl; //打印weight数组，这里面存放的是，所有物品在背包只有空间i的时候，达到的最大总价值。 } int backPackSpace = volumeOfBackpack;// 得到背包空间 //通过查找最后相同的数量得到实际的体积 while (weight[backPackSpace] == weight[backPackSpace-1]) { backPackSpace--;//假如背包价值和背包空间-1的时候价值相同，空间 -1 }//找到一共使用了多少空间（只压缩最后一个） //顺藤摸瓜找物品 for (int i = 0; i < numberOfStone; ++i) { if (weight[backPackSpace] == weight[backPackSpace-stoneVolume[i]] + stoneWeight[i]) //假如减去当前物品的空间，总价值刚好和物品的价值相等，说明此物品被放入了。 { //打印这个物品。i+1是因为物品的下标是从0开始的。 cout<<stoneVolume[i]<<"\t"<<stoneWeight[i]<<"\t Location: "<<i+1<<endl; backPackSpace = backPackSpace - stoneVolume[i]; //背包放入了这个物品，自然空间减少了。 } } return 0; } /* 5 10 4 9 3 6 5 1 2 4 5 1 19 */ int stoneVolume[numberOfStone] = {4,3,6,11,5}; int stoneWeight[numberOfStone] = {1,6,11,41,11}; //上面的代码只能找出3 6 不能找出来3 5