2019独角兽企业重金招聘Python工程师标准>>> 
背包问题，我就知道有零一背包和分数背包。零一背包看了就忘，想起来再看，再看再忘。
分数背包没怎么看过，也没怎么记住。今天心血来潮，在网上找到了一段代码（本段代码来自百度的一个叫“冰蓝沸点”的空间，地址：http://hi.baidu.com/nikopolidis/item/d31f4316997bb6ce38cb3064。我做了一下格式化），如下：
#include <iostream>
#include <cstdlib>
#include <ctime>using namespace std;class bag{private:int id;int weight;int profit;public:bag(){};bag(int i, int w, int p):id(i), weight(w), profit(p){}int getID(){return id;}int getWeight(){return weight;}int getProfit(){return profit;}double getValue(){return ((double) profit/(double) weight);}bag& operator=(bag &a);
};bag& bag::operator=(bag &a)
{id = a.id;weight = a.weight;profit = a.profit;return *this;
}bool operator<(bag &a, bag &b)
{double aValue, bValue;aValue = a.getValue();bValue = b.getValue();return (aValue<bValue ? true : false);
}void arrayPrint(bag *a, int n)
{for(int i = 0; i < n; i++)cout << a[i].getID() << " ";cout << endl;
}void selectionSort(bag *a, int n)
{for(int i = 0; i < n; i++){int min = i;for(int j = i + 1; j < n; j++){if(a[j] < a[min])min = j;}swap(a[i], a[min]);}
}void knapsack(bag *a, int n, double limitWeight)
{selectionSort(a, n);double curWeight = 0.0;double curProfit = 0.0;for(int i = n - 1; i >= 0; i--){if(curWeight + a[i].getWeight() <= limitWeight){cout << a[i].getID() << "(1)" << " ";curWeight += a[i].getWeight();curProfit += a[i].getProfit();if(curWeight == limitWeight){cout << endl;break ;}}else{double propotion = (limitWeight - curWeight) / a[i].getWeight();curWeight += (a[i].getWeight() * propotion);curProfit += (a[i].getProfit() * propotion);cout << a[i].getID() << "(" << propotion << ")" << endl;break ;}}cout << "Total profit: " << curProfit << ".\n";
}int main()
{int weight1 = 2, weight2 = 4, weight3 = 1000,profit1 = 1000, profit2 = 20, profit3 = 20;bag a(2, weight1, profit1);bag b(1, weight2, profit2);bag c(0, weight3, profit3);bag *bagArray = new bag[3];bagArray[0] = a, bagArray[1] = b, bagArray[2] = c;knapsack(bagArray, 3, 5.0);return 0;
}看完代码，明白了。
分数背包要解决的问题是这样的：有个背包和一堆细软。要把细软装到包里。如果细软太大(或者太重)装不进去的话，可以剁碎了变成小细软。现在让你把包装满，并且达到包里的细软总价值最大的效果。至于为什么是背包，而不是挎包，行李箱之类的东西，这我就不知道了。可能就是个抽象含义吧，就是指一个容器了。
解决的思路大概就是这么个意思：先把细软按照单位重量(或者体积)的价值进行排序，然后先可最贵的往包里装，装不下就切成小块装，最贵的装完，装第二贵的，以此类推。直到装满，就算是完事儿了。连个递归的过程都用不上。
看来，似乎分数背包比零一背包问题还简单一些啊。
我知道的背包问题，不管是分数背包或者零一背包，都是只限制一个条件：重量或者是体积。其实这俩限制本质上是一样的啦。然后我现在就有个问题：如果背包既限制重量，又限制体积呢？那么该怎么算？
唉，本人比较懒，先把这个问题冷处理吧。冷处理，是高中时候一个同桌自创的处理问题方法，就是把眼下想不出来的问题冷冻起来。等哪天突然灵光一现的时候，再拿出来研究。说白了就是拖延啦。
也欢迎各位大神能指点一二。不胜感谢。
