浅谈java实现背包算法(0-1背包问题)
0-1背包的问题
背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
这是最基础的背包问题，特点是:每种物品仅有一件，可以选择放或不放。
用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:
f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+v[i]}。
publicclassBag{
staticclassItem{//定义一个物品
Stringid;//物品id
intsize=0;//物品所占空间
intvalue=0;//物品价值
staticItemnewItem(Stringid,intsize,intvalue){
Itemitem=newItem();
item.id=id;
item.size=size;
item.value=value;
returnitem;
}
publicStringtoString(){
returnthis.id;
}
}
staticclassOkBag{//定义一个打包方式
List- Items=newArrayList
- ();//包里的物品集合
OkBag(){
}
intgetValue(){//包中物品的总价值
intvalue=0;
for(Itemitem:Items){
value+=item.value;
}
returnvalue;
};
intgetSize(){//包中物品的总大小
intsize=0;
for(Itemitem:Items){
size+=item.size;
}
returnsize;
};
publicStringtoString(){
returnString.valueOf(this.getValue())+"";
}
}
//可放入包中的备选物品
staticItem[]sourceItems={Item.newItem("4号球",4,5),Item.newItem("5号球",5,6),Item.newItem("6号球",6,7)};
staticintbagSize=10;//包的空间
staticintitemCount=sourceItems.length;//物品的数量
//保存各种情况下的最优打包方式第一维度为物品数量从0到itemCount,第二维度为包裹大小从0到bagSize
staticOkBag[][]okBags=newOkBag[itemCount+1][bagSize+1];
staticvoidinit(){
for(inti=0;i
curBagSize){//当前物品大于包空间.肯定不能放入包中.
okBags[iItem][curBagSize].Items.addAll(okBags[iItem-1][curBagSize].Items);
}else{
intnotIncludeValue=okBags[iItem-1][curBagSize].getValue();//不放当前物品包的价值
intfreeSize=curBagSize-sourceItems[iItem-1].size;//放当前物品包剩余空间
intincludeValue=sourceItems[iItem-1].value+okBags[iItem-1][freeSize].getValue();//当前物品价值+放了当前物品后剩余包空间能放物品的价值
if(notIncludeValue
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。