背包问题，我就知道有零一背包和分数背包。零一背包看了就忘，想起来再看，再看再忘。

分数背包没怎么看过，也没怎么记住。今天心血来潮，在网上找到了一段代码（本段代码来自百度的一个叫“冰蓝沸点”的空间，地址：。我做了一下格式化），如下：

#include 
    
     #include 
     
      #include 
      
       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
       
        = 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;}
       
      
     
    

       看完代码，明白了。

       分数背包要解决的问题是这样的：有个背包和一堆细软。要把细软装到包里。如果细软太大(或者太重)装不进去的话，可以剁碎了变成小细软。现在让你把包装满，并且达到包里的细软总价值最大的效果。至于为什么是背包，而不是挎包，行李箱之类的东西，这我就不知道了。可能就是个抽象含义吧，就是指一个容器了。

       解决的思路大概就是这么个意思：先把细软按照单位重量(或者体积)的价值进行排序，然后先可最贵的往包里装，装不下就切成小块装，最贵的装完，装第二贵的，以此类推。直到装满，就算是完事儿了。连个递归的过程都用不上。

看来，似乎分数背包比零一背包问题还简单一些啊。

       我知道的背包问题，不管是分数背包或者零一背包，都是只限制一个条件：重量或者是体积。其实这俩限制本质上是一样的啦。然后我现在就有个问题：如果背包既限制重量，又限制体积呢？那么该怎么算？

        唉，本人比较懒，先把这个问题冷处理吧。冷处理，是高中时候一个同桌自创的处理问题方法，就是把眼下想不出来的问题冷冻起来。等哪天突然灵光一现的时候，再拿出来研究。说白了就是拖延啦。

       也欢迎各位大神能指点一二。不胜感谢。