0-1多维背包多维、背包
2023-09-11 23:19:38
作者：夏日⊕樱花
所以我想生成算法，将发现的n项（在我的情况4）的最佳组合，只能放置在背包一次（0-1），最大承重能力。可能更有效地归纳总结，我希望把不超过四个独特的项目在我的背包，以使它们的权重低于一定值，同时最大限度地提高他们的总值W。我的第一次尝试，并假设是把4的音量限制所有的项目数量为1多维背包问题。不过，我跑进这不是0-1（意为无论是在袋子与否）的问题。然后我试图做一个0-1（界）背包code多方面的，但我无法添加量的限制，以及0-1的要求。我如何codeA 0-1多维背包问题？或者，我该如何适应code到只能容纳体积V的所有项目数量为1？在code不必须是Java的，但是这是我到目前为止所。
背包：
包hu.pj.alg;
进口hu.pj.obj.Item;
导入的java.util。*;
公共类ZeroOneKnapsack {
受保护的名单，其中，项目＆GT; ITEMLIST =新的ArrayList＆LT;项目＆GT;（）;
保护INT maxWeight = 0;
保护INT solutionWeight = 0;
保护INT利润= 0;
计算值=假保护的布尔值;
公共ZeroOneKnapsack（）{}
公共ZeroOneKnapsack（INT _maxWeight）{
setMaxWeight（_maxWeight）;
}
公共ZeroOneKnapsack（名单＆LT;项目＆GT; _itemList）{
setItemList（_itemList）;
}
公共ZeroOneKnapsack（名单＆LT;项目＆GT; _itemList，INT _maxWeight）{
setItemList（_itemList）;
setMaxWeight（_maxWeight）;
}
// calculte 0-1背包问题的动态方法解决：
公开名单＆LT;项目＆GT; calcSolution（）{
INT N = itemList.size（）;
setInitialStateForCalculation（）;
如果（正大于0＆安培;＆安培; maxWeight大于0）{
名单＆LT;名单＆LT;整数GT; ＆GT; C =新的ArrayList＆LT;名单＆LT;整数GT; ＆GT;（）;
名单＆LT;整数GT; CURR =新的ArrayList＆LT;整数GT;（）;
c.add（CURR）;
对于（INT J = 0; J＆LT; = maxWeight; J ++）
curr.add（0）;
的for（int i = 1; I＆LT; = N;我++）{
名单＆LT;整数GT; preV = CURR;
c.add（CURR =新的ArrayList＆其中;整数＆GT;（））;
对于（INT J = 0; J＆LT; = maxWeight; J ++）{
如果（J＆0）{
INT WH = itemList.get第（i-1）.getWeight（）;
curr.add（
（WH＆GT; j）条
？
prev.get（J）
：
Math.max（
prev.get（J）
itemList.get第（i-1）.getValue（）+ prev.get（J-WH）
）
）;
} 其他 {
curr.add（0）;
}
} //为（十...）
} //为（我...）
利润= curr.get（maxWeight）;
的for（int i = N时，J = maxWeight;我大于0＆安培;＆安培; J＆GT; = 0; I--）{
INT TEMPI = c.get（I）获得（j）条;
INT tempI_1 = c.get第（i-1）获得（j）条;
如果 （
（我== 0安培;＆安培; TEMPI大于0）
||
（ⅰ大于0＆安培;＆安培; TEMPI = tempI_1！）
）
{
项IH = itemList.get第（i-1）;
INT WH = iH.getWeight（）;
iH.setInKnapsack（1）;
的J - =瓦时;
solutionWeight + = WH;
}
} // 对于（）
计算值=真;
} // 如果（）
返回ITEMLIST;
}
//项目添加到项目列表
公共无效添加（字符串名称，诠释权重，int值）{
如果（name.equals（））
名称=+（itemList.size（）+ 1）;
itemList.add（新项目（名称，重量，价值））;
setInitialStateForCalculation（）;
}
//项目添加到项目列表
公共无效添加（INT重量，int值）{
加（，重量，价值）; //这个名字将是itemList.size（）+ 1！
}
//从项列表中删除项目
公共无效删除（字符串名称）{
对（迭代器＆LT;项目＆gt;其= itemList.iterator（）; it.hasNext（））{
如果（name.equals（it.next（）。的getName（）））{
it.remove（）;
}
}
setInitialStateForCalculation（）;
}
//删除该项目列表中的所有项目
公共无效removeAllItems（）{
itemList.clear（）;
setInitialStateForCalculation（）;
}
公众诠释getProfit（）{
如果（！计算）
calcSolution（）;
返回的利润;
}
公众诠释getSolutionWeight（）{返回solutionWeight;}
公共布尔isCalculated（）{回报计算;}
公众诠释getMaxWeight（）{返回maxWeight;}
公共无效setMaxWeight（INT _maxWeight）{
maxWeight = Math.max（_maxWeight，0）;
}
公共无效setItemList（名单＆LT;项目＆GT; _itemList）{
如果（_itemList！= NULL）{
ITEMLIST = _itemList;
为（项目编号：_itemList）{
item.checkMembers（）;
}
}
}
//设置名称为inKnapsack所有的项目成员：
私人无效setInKnapsackByAll（INT inKnapsack）{
为（项目编号：ITEMLIST）
如果（inKnapsack大于0）
item.setInKnapsack（1）;
其他
item.setInKnapsack（0）;
}
//设置类的数据成员开始计算的状态：
保护无效setInitialStateForCalculation（）{
setInKnapsackByAll（0）;
计算值= FALSE;
利润= 0;
solutionWeight = 0;
}
} // 类
，而该项目：
包hu.pj.obj;
公共类项目{
受保护的字符串名称=;
保护INT重量= 0;
保护int值= 0;
保护INT边界= 1; //项目的棋子的最大极限
保护INT inKnapsack = 0; //项在溶液中的片
公共项目（）{}
公共项目（编号项）{
setname可以（item.name）;
setWeight（item.weight）;
的setValue（item.value）;
setBounding（item.bounding）;
}
公共项目（INT _weight，诠释_value）{
setWeight（_weight）;
的setValue（_value）;
}
公共项目（INT _weight，诠释_value，诠释_bounding）{
setWeight（_weight）;
的setValue（_value）;
setBounding（_bounding）;
}
公共项目（字符串_name，诠释_weight，诠释_value）{
setname可以（_name）;
setWeight（_weight）;
的setValue（_value）;
}
公共项目（字符串_name，诠释_weight，诠释_value，诠释_bounding）{
setname可以（_name）;
setWeight（_weight）;
的setValue（_value）;
setBounding（_bounding）;
}
公共无效setname可以（字符串_name）{name = _name;}
公共无效setWeight（INT _weight）{重量= Math.max（_weight，0）;}
公共无效的setValue（INT _value）{值= Math.max（_value，0）;}
公共无效setInKnapsack（INT _inKnapsack）{
inKnapsack = Math.min（getBounding（），Math.max（_inKnapsack，0））;
}
公共无效setBounding（INT _bounding）{
边界= Math.max（_bounding，0）;
如果（边界== 0）
inKnapsack = 0;
}
公共无效checkMembers（）{
setWeight（重量）;
的setValue（值）;
setBounding（边界）;
setInKnapsack（inKnapsack）;
}
公共字符串的getName（）{返回名字;}
公众诠释getWeight（）{返回重;}
公众诠释的getValue（）{返回值;}
公众诠释getInKnapsack（）{返回inKnapsack;}
公众诠释getBounding（）{返回边界;}
} // 类
解决方案 
下面是一个通用的实施，解决了背包0-1问题2尺寸（尺寸和体积）。我用一个矩阵，而不是列表的名单，因为它要容易得多。这里是整个类也来测试它的主要方法。 要添加尺寸只是新的维度添加到矩阵，并添加内循环，检查所有条件。
公共类MultidimensionalKnapsack {
/ **背包的大小* /
私有静态诠释大小;
/ **背包的体积* /
私有静态诠释卷;
私有静态类项目{
公共int值;
公众诠释大小;
公众诠释量;
公共项目（INT V，INT W，INT体积）{
值= V;
大小= W;
体积=体积;
}
}
//背包0/1不重复
//行：其仅在第i个项目的问题
//西：有大小j的背包问题
//第三个维度：具有体积小时的背包问题
私有静态诠释[] [] [] dynNoRep;
私有静态无效noRep（第[]项）{
dynNoRep =新INT [items.length + 1] [尺寸+ 1] [VOL + 1];
对于（INT J = 0; J＆LT; =大小; J ++）{
dynNoRep [0] [j]的[0] = 0;
}
的for（int i = 0; I＆LT; =体积;我++）{
dynNoRep [0] [0] [I] = 0;
}
的for（int i = 0; I＆LT; = items.length;我++）{
dynNoRep [I] [0] [0] = 0;
}
的for（int i = 1; I＆LT; = items.length;我++）
对于（INT J = 0; J＆LT; =大小; J ++）{
为（中间体H = 0; H＆其中; =体积; H ++）{
如果（项目[我 - 1] .size＆GT; j）条
//如果这个项目我是太大了，我不能把它和解决方案是相同的问题与我 - 1项
dynNoRep [i] [j]的[H] = dynNoRep [我 - 1] [j]的[H]
其他 {
如果（项目[我 - 1] .volume＆GT; H）
//如果项目我实在太庞大，我不能把它和解决方案是相同的问题与我 - 1项
dynNoRep [i] [j]的[H] = dynNoRep [我 - 1] [j]的[H]
其他 {
//该项目i可以是无用的，该溶液是相同的问题，其中i - 1项，或它可以是
//有用并将该溶液是（大小的J背包的溶液 - 项[I] .size和体积ħ - 项[I] .volume）+项[I]。价值
dynNoRep [i] [j]的[H] = Math.max（dynNoRep [我 - 1] [j]的[H]，dynNoRep [我 - 1] [J - 项目[我 - 1] .size] [H - 项目[我 - 1] .volume] +项目[我 - 1]。价值）;
}
}
}
}
}
公共静态无效的主要（字串[] args）{
大小= 15;
体积= 12;
项目[]项目= {新的项目（2，4，1），新的项目（1，5，4）新的项目（6,3，9），
新的项目（3,3，19），新项目（7,2，7），新的项目（1，2，6），新的项目（2，1，2）
新的项目（10，9，12），新的项目（9，10，2）新的项目（24，23，11）};
System.out.print（我们下面的+ items.length +项目（值，大小，数量）：）;
的for（int i = 0; I＆LT; items.length;我++）
System.out.print（（+项[I]。价值+，+项[I] .size +，+项[I] .volume +））;
的System.out.println（）;
的System.out.println（和大小的背包+规模+和音量+体积）;
noRep（项目）;
的System.out.println（）;
//打印解决方案
诠释J =大小中，h =体积，finalSize = 0，finalValue = 0，finalVolume = 0;
System.out.print（项目挑（值，大小，体积比）为0/1的问题不重复：）;
的for（int i = items.length; I＆GT; 0;我 - ）{
如果（dynNoRep [i] [j]的[H] = dynNoRep [我 - 1]！[J] [H]）{
System.out.print（（+项[I - 1]。价值+，+项[I - 1] .size +，+项[I - 1] .volume +））;
finalSize + =项[我 - 1] .size;
finalValue + =项[我 - 1] .value的;
finalVolume + =项[我 - 1] .volume;
的J - =项[我 - 1] .size;
^ h - =项[我 - 1] .volume;
}
}
的System.out.println（）;
的System.out.println（最后的大小：+ finalSize）;
的System.out.println（最终卷上：+ finalVolume）;
的System.out.println（终值+ finalValue）;
}
}
So I'm trying to generate an algorithm that will find the best combination of n items (in my case 4) that can only be placed in the knapsack once (0-1) with a maximum weight capacity. Summarized probably more effectively, I want to place no more than four unique items in my knapsack so that the their weights are less than some value W while maximizing their total value. My first attempt and assumption was to put a volume limit of 4 with all item volumes as 1 for a multidimensional knapsack problem. But I ran into the problem of it not being 0-1 (meaning either in the bag or not). Then I tried making an 0-1(bounded) knapsack code multidimensional but I was unable to add the volume limit as well as the 0-1 requirement. How do I code a 0-1 multidimensional knapsack problem? Or how do I adapt the code to only hold a volume of V with all item volumes as 1? The code doesnt have to be Java but that's what I have so far.
The Knapsack:
package hu.pj.alg;
import hu.pj.obj.Item;
import java.util.*;
public class ZeroOneKnapsack {
protected List<Item> itemList = new ArrayList<Item>();
protected int maxWeight = 0;
protected int solutionWeight = 0;
protected int profit = 0;
protected boolean calculated = false;
public ZeroOneKnapsack() {}
public ZeroOneKnapsack(int _maxWeight) {
setMaxWeight(_maxWeight);
}
public ZeroOneKnapsack(List<Item> _itemList) {
setItemList(_itemList);
}
public ZeroOneKnapsack(List<Item> _itemList, int _maxWeight) {
setItemList(_itemList);
setMaxWeight(_maxWeight);
}
// calculte the solution of 0-1 knapsack problem with dynamic method:
public List<Item> calcSolution() {
int n = itemList.size();
setInitialStateForCalculation();
if (n > 0 && maxWeight > 0) {
List< List<Integer> > c = new ArrayList< List<Integer> >();
List<Integer> curr = new ArrayList<Integer>();
c.add(curr);
for (int j = 0; j <= maxWeight; j++)
curr.add(0);
for (int i = 1; i <= n; i++) {
List<Integer> prev = curr;
c.add(curr = new ArrayList<Integer>());
for (int j = 0; j <= maxWeight; j++) {
if (j > 0) {
int wH = itemList.get(i-1).getWeight();
curr.add(
(wH > j)
?
prev.get(j)
:
Math.max(
prev.get(j),
itemList.get(i-1).getValue() + prev.get(j-wH)
)
);
} else {
curr.add(0);
}
} // for (j...)
} // for (i...)
profit = curr.get(maxWeight);
for (int i = n, j = maxWeight; i > 0 && j >= 0; i--) {
int tempI = c.get(i).get(j);
int tempI_1 = c.get(i-1).get(j);
if (
(i == 0 && tempI > 0)
||
(i > 0 && tempI != tempI_1)
)
{
Item iH = itemList.get(i-1);
int wH = iH.getWeight();
iH.setInKnapsack(1);
j -= wH;
solutionWeight += wH;
}
} // for()
calculated = true;
} // if()
return itemList;
}
// add an item to the item list
public void add(String name, int weight, int value) {
if (name.equals(""))
name = "" + (itemList.size() + 1);
itemList.add(new Item(name, weight, value));
setInitialStateForCalculation();
}
// add an item to the item list
public void add(int weight, int value) {
add("", weight, value); // the name will be "itemList.size() + 1"!
}
// remove an item from the item list
public void remove(String name) {
for (Iterator<Item> it = itemList.iterator(); it.hasNext(); ) {
if (name.equals(it.next().getName())) {
it.remove();
}
}
setInitialStateForCalculation();
}
// remove all items from the item list
public void removeAllItems() {
itemList.clear();
setInitialStateForCalculation();
}
public int getProfit() {
if (!calculated)
calcSolution();
return profit;
}
public int getSolutionWeight() {return solutionWeight;}
public boolean isCalculated() {return calculated;}
public int getMaxWeight() {return maxWeight;}
public void setMaxWeight(int _maxWeight) {
maxWeight = Math.max(_maxWeight, 0);
}
public void setItemList(List<Item> _itemList) {
if (_itemList != null) {
itemList = _itemList;
for (Item item : _itemList) {
item.checkMembers();
}
}
}
// set the member with name "inKnapsack" by all items:
private void setInKnapsackByAll(int inKnapsack) {
for (Item item : itemList)
if (inKnapsack > 0)
item.setInKnapsack(1);
else
item.setInKnapsack(0);
}
// set the data members of class in the state of starting the calculation:
protected void setInitialStateForCalculation() {
setInKnapsackByAll(0);
calculated = false;
profit = 0;
solutionWeight = 0;
}
} // class
And the Item:
package hu.pj.obj;
public class Item {
protected String name = "";
protected int weight = 0;
protected int value = 0;
protected int bounding = 1; // the maximal limit of item's pieces
protected int inKnapsack = 0; // the pieces of item in solution
public Item() {}
public Item(Item item) {
setName(item.name);
setWeight(item.weight);
setValue(item.value);
setBounding(item.bounding);
}
public Item(int _weight, int _value) {
setWeight(_weight);
setValue(_value);
}
public Item(int _weight, int _value, int _bounding) {
setWeight(_weight);
setValue(_value);
setBounding(_bounding);
}
public Item(String _name, int _weight, int _value) {
setName(_name);
setWeight(_weight);
setValue(_value);
}
public Item(String _name, int _weight, int _value, int _bounding) {
setName(_name);
setWeight(_weight);
setValue(_value);
setBounding(_bounding);
}
public void setName(String _name) {name = _name;}
public void setWeight(int _weight) {weight = Math.max(_weight, 0);}
public void setValue(int _value) {value = Math.max(_value, 0);}
public void setInKnapsack(int _inKnapsack) {
inKnapsack = Math.min(getBounding(), Math.max(_inKnapsack, 0));
}
public void setBounding(int _bounding) {
bounding = Math.max(_bounding, 0);
if (bounding == 0)
inKnapsack = 0;
}
public void checkMembers() {
setWeight(weight);
setValue(value);
setBounding(bounding);
setInKnapsack(inKnapsack);
}
public String getName() {return name;}
public int getWeight() {return weight;}
public int getValue() {return value;}
public int getInKnapsack() {return inKnapsack;}
public int getBounding() {return bounding;}
} // class
解决方案
Here is a generic implementation to solve the knapsack 0-1 problem with 2 dimensions (size and volume). I used a matrix instead of a list of list because it is much easier. Here is the whole class with also the main method to test it. To add dimensions just add new dimensions to the matrix and add inner cycles to check all conditions.
public class MultidimensionalKnapsack {
/** The size of the knapsack */
private static int size;
/** The volume of the knapsack */
private static int vol;
private static class Item {
public int value;
public int size;
public int volume;
public Item(int v, int w, int vol) {
value = v;
size = w;
volume = vol;
}
}
// Knapsack 0/1 without repetition
// Row: problem having only the first i items
// Col: problem having a knapsack of size j
// Third dimension: problem having a knapsack of volume h
private static int[][][] dynNoRep;
private static void noRep(Item[] items) {
dynNoRep = new int[items.length + 1][size + 1][vol + 1];
for(int j = 0; j <= size; j++) {
dynNoRep[0][j][0] = 0;
}
for(int i = 0; i <= vol; i++) {
dynNoRep[0][0][i] = 0;
}
for(int i = 0; i <= items.length; i++) {
dynNoRep[i][0][0] = 0;
}
for(int i = 1; i <= items.length; i++)
for(int j = 0; j <= size; j++) {
for(int h = 0; h <= vol; h++) {
if(items[i - 1].size > j)
// If the item i is too big, I can't put it and the solution is the same of the problem with i - 1 items
dynNoRep[i][j][h] = dynNoRep[i - 1][j][h];
else {
if(items[i - 1].volume > h)
// If the item i is too voluminous, I can't put it and the solution is the same of the problem with i - 1 items
dynNoRep[i][j][h] = dynNoRep[i - 1][j][h];
else {
// The item i could be useless and the solution is the same of the problem with i - 1 items, or it could be
// useful and the solution is "(solution of knapsack of size j - item[i].size and volume h - item[i].volume) + item[i].value"
dynNoRep[i][j][h] = Math.max(dynNoRep[i - 1][j][h], dynNoRep[i - 1][j - items[i - 1].size][h - items[i - 1].volume] + items[i - 1].value);
}
}
}
}
}
public static void main(String[] args) {
size = 15;
vol = 12;
Item[] items = {new Item(2, 4, 1), new Item(1, 5, 4), new Item(6, 3, 9),
new Item(3, 3, 19), new Item(7, 2, 7), new Item(1, 2, 6), new Item(2, 1, 2),
new Item(10, 9, 12), new Item(9, 10, 2), new Item(24, 23, 11)};
System.out.print("We have the following " + items.length + " items (value, size, volume): ");
for(int i = 0; i < items.length; i++)
System.out.print("(" + items[i].value + ", " + items[i].size + ", " + items[i].volume + ") ");
System.out.println();
System.out.println("And a knapsack of size " + size + " and volume " + vol);
noRep(items);
System.out.println();
// Print the solution
int j = size, h = vol, finalSize = 0, finalValue = 0, finalVolume = 0;
System.out.print("Items picked (value, size, volume) for 0/1 problems without repetitions: ");
for(int i = items.length; i > 0; i--) {
if(dynNoRep[i][j][h] != dynNoRep[i - 1][j][h]) {
System.out.print("(" + items[i - 1].value + ", " + items[i - 1].size + ", " + items[i - 1].volume + ") ");
finalSize += items[i - 1].size;
finalValue += items[i - 1].value;
finalVolume += items[i - 1].volume;
j -= items[i - 1].size;
h -= items[i - 1].volume;
}
}
System.out.println();
System.out.println(" Final size: " + finalSize);
System.out.println(" Final volume: " + finalVolume);
System.out.println(" Final value: " + finalValue);
}
}
上一篇：C ++排序算法算法
相关推荐
猜您喜欢
精彩图集
