Given n items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.
## 1.
Relax the [[Knapsack Problem]] to obtain an upper bound.
>[!hint]-
>Look at the remaining items, drop the 0-1 constraint, so
>getting a fraction of an item is allowed and gives you
>the corresponding fraction of its value. Design an algorithm that
>solves the new problem correctly (make the solution your upper bound).
```python
# Given "WeightMax" to be the weight of your bag
# Assume this to be a sorted set from greatest ratio to lowest
SortedItems = SortedArray()
Value = 0
WeightAccumulation = 0
while not SortedItems.Empty():
Item = SortedItems.Pop()
if Item.Weight + WeightAccumulation > WeightMax:
break
Value += Item.Value
WeightAccumulation += Item.Weight
return Value
```
## 2.
Provide pseudo code for branch and bound algorithm that
uses the above relaxed problem as upper bound.
Especially the inequality that will be used to cancel branching.
Provide recursive version.
```python
def BranchAndBound(Index, CurrentWeight, CurrentValue, Items, Capacity, BestValueFound):
if Index > Items.Length or CurrentWeight == Capacity:
return max(BestValueFound, CurrentValue)
# Assume this FractionUpperBound to be the previous question's pseudocode but for a slice of the array from Index to the length of items
Bound = CurrentValue + FractionUpperBound(Items, Index, Capacity - CurrentWeight)
if Bound <= BestValueFound:
return BestValueFound
if CurrentWeight + Items[Index].Weight <= Capacity:
BestValueFound = BranchAndBound(Index + 1, CurrentWeight + Items[i].Weight, CurrentValue + Items[i].Value, Items, Capacity, BestValueFound)
BestValueFound = BranchAndBound(Index + 1, CurrentWeight, CurrentValue, Items, Capacity, BestValueFound)
return BestValue
```
## 3.
Consider the following bin-packing problem:
You are packing card-board boxes to move your stuff to a new apartment.
The items have weights `w[i]` where $i=1,\dots, n$.
The volume of the item is not important for this problem --
Think all items have the same size (volume) and box can fit any number of items.
Each card-board box can hold up to M total weight. Your goal is to pack
into as few boxes as possible.
Example: $M=5$, weights of items are 2,4,3,2,3,3. One packing may be
2+3, 4, 2+3,3 for a total of 4 boxes.
Another is 2+2, 4, 3, 3 ,3 for a total of 5 boxes. The first solution is better then the second (and actually optimal).
Relax the bin-packing problem to obtain a lower bound.
The lowest bound would be the `ceil` of the total weight of all items divided by the maximum weight capacity per box.
4.
Provide pseudo code for branch and bound algorithm that
uses the above relaxed problem as lower bound.
Especially the inequality that will be used to cancel branching.
Provide iterative version that uses dynamic data structure
to mimic recursion.
```python
Weights = [ ... ]
# Assume weights are sorted
class PackState:
Index: int
Boxes: [int]
RemainingWeight: int
N = Weights.Length
TotalWeight = sum(Weights)
Best = Weights.Length
BestPacking = None
Stack = [PackState(0, [], TotalWeight)]
while not Stack.Empty():
(Index, Boxes, WeightRemaining) = Stack.Pop()
if Index == Weights.Length:
if Boxes.Length < Best:
Best = len(Boxes)
BestPacking = Boxes
continue
Weight = Weights[Index]
Remaining = CountLargerThan(Weights, Index, MaxWeightPerBox)
LowerBound = Boxes.Length + max(ceil( WeightRemaining / MaxWeightPerBox), Remaining)
if LowerBound >= Best:
continue
for K in 0..Boxes.Length:
if Boxes[K] + Weight <= MaxWeightPerBox:
NewBoxes = Boxes.Copy()
NewBoxes[k] += Weight
Stack.Push(PackState(Index + 1, NewBoxes, WeightRemaining - Weight))
NewBoxes = Boxes.Copy()
NweBoxes.Add(Weight)
Stack.Push(PackState(Index + 1, NewBoxes, WeightRemaining - Weight))
```
Example answer:
===============
based on the job assignment problem from class:
lower bound:
relax the problem by removing the condition that all jobs have to be assigned, i.e.
same job may be assigned to two or more workers.
The corresponding lower bound is "for each remaining worker find the cheapest remaining job":
Algorithm:
```c++
rec( ... ) {
if ( assignment is complete ) {
compare to the best so far and update BSF if needed;
retrun;
}
LB = calculate lower bound
if ( current cost + LB >= BSF ) return; // cancel branch
for each remaining job {
assign job to current worker
rec call
}
}
```
Conversion to iterative
```c++
iterative_solution( .... ) {
stack.push( empty )
while ( stack not empty ) {
A = stack.pop()
// is it base case
if ( A is complete ) { // all jobs assigned
if ( cost < BSF ) BSF = cost
continue;
}
// else
LB = calculate lower bound
if ( cost + LB >= BSF ) continue;
for each remaining job J {
stack.push( A + J )
}
} // while
return BSF
}
```