Skip to content

Instantly share code, notes, and snippets.

@nvshah

nvshah/KnapSack.py

Last active June 16, 2020 13:55
Show Gist options
  • Save nvshah/0363eb9ee85908fdf28f9bcc502d7db1 to your computer and use it in GitHub Desktop.
Save nvshah/0363eb9ee85908fdf28f9bcc502d7db1 to your computer and use it in GitHub Desktop.
Download ZIP
Dynamic Programming - KnapSack Problem
Raw
KnapSack.py
from enum import Enum
import logging
### Globals-------------------------------------------------------------------------------------------------------------------
selectedItems = [] # current set of item that form the solution
Matrix_PossibleWays_RepeatOFF = [] # Each member represents the max value possible with given items
Matrix_PossibleWays_RepeatON = [] # Each member represents the max value possible with given items , repeatation of items is allowed
Matrix_MinimalItems_RepeatOFF = [] # Each member represents the (min weight, max value, min items) possible with given items
Matrix_MinimalItems_RepeatON = [] # Each member represents the (min weight, max value, min items) possible with given items, repeatation of items is allowed
PossibleSack_RepeatOFF = [] # List containing all possible items combinations
PossibleSack_RepeatON = [] # List containing all possible items combinations, repeat of items is allowed
MinimalSack_RepeatOFF = [] # List containing only items combinations that leads to min weight of sack, max value of sack & min items in sack;
MinimalSack_RepeatON = [] # List containing only items combinations that leads to min weight of sack, max value of sack & min items in sack; repeat of items is allowed
currentRow = [] # Used while creating matrix when repeatation of element is allowed
totalValue = 0 # max value of sack that can be possible
#possibilities of cases to look for | 4 different Scenarios
Cases = Enum('Cases', 'NonRepeat,Repeat,MinimalNonRepeat,MinimalRepeat')
### Functions-------------------------------------------------------------------------------------------------------------------
def prepareMatrix(matrix, memberFeeder, repeat = False):
'''
Prepare a matrix according to the case
'''
#logging.info('Preparing Matrix ... ')
if repeat:
for item in range(N+1):
currentRow.clear()
for weight in range(M+1):
currentRow.append(memberFeeder(item, weight))
matrix.append(currentRow.copy())
else:
for item in range(N+1):
matrix.append([memberFeeder(item, weight) for weight in range(M+1)])
#for row in matrix:
#print(row)
def memberFeeder_PossibleWays_RepeatOFF(index, weight):
'''
Use to calculate & imbue each member of matrix | It will feed a matrix, that is used to find all possible combinations of items
(Repeatation of items is not allowed)
'''
if weight == 0 or index == 0:
return 0
if items[index][0] <= weight:
return max(Matrix_PossibleWays_RepeatOFF[index-1][weight], items[index][1] + Matrix_PossibleWays_RepeatOFF[index-1][weight - items[index][0]])
else:
return Matrix_PossibleWays_RepeatOFF[index-1][weight]
def memberFeeder_PossibleWays_RepeatON(index, weight):
'''
Use to calculate & imbue each member of matrix | It will feed a matrix, that is used to find all possible combinations of items
(Repeatation of items is allowed)
'''
if weight == 0 or index == 0:
return 0
if items[index][0] <= weight:
return max(Matrix_PossibleWays_RepeatON[index-1][weight], items[index][1] + currentRow[weight - items[index][0]])
else:
return Matrix_PossibleWays_RepeatON[index-1][weight]
def memberFeeder_MinimalItems_RepeatOFF(index, weight):
'''
Use to calculate & imbue each member of matrix | It will feed a matrix, that is used to find all minimal possible combinations of items
(Repeatation of items is not allowed)
Minimal solution :- Max Value with Minimum Weight and Minimum Quantity
'''
if weight == 0 or index == 0:
return (0, 0, 0)
oldElement = Matrix_MinimalItems_RepeatOFF[index-1][weight]
if items[index][0] <= weight:
newValue = items[index][1] + Matrix_MinimalItems_RepeatOFF[index-1][weight - items[index][0]][1]
newWeight = items[index][0] + Matrix_MinimalItems_RepeatOFF[index-1][weight - items[index][0]][0]
newCount = 1 + Matrix_MinimalItems_RepeatOFF[index-1][weight - items[index][0]][2]
newElement = (newWeight, newValue, newCount)
if newValue > oldElement[1]:
return newElement
if newValue == oldElement[1]:
if newWeight < oldElement[0]:
return newElement
elif newWeight == oldElement[0]:
if newCount <= oldElement[2]:
return newElement
return oldElement
else:
return oldElement
def memberFeeder_MinimalItems_RepeatON(index, weight):
'''
Use to calculate & imbue each member of matrix | It will feed a matrix, that is used to find all minimal possible combinations of items
(Repeatation of items is allowed)
Minimal solution :- Max Value with Minimum Weight and Minimum Quantity
'''
if weight == 0 or index == 0:
return (0, 0, 0)
oldElement = Matrix_MinimalItems_RepeatON[index-1][weight]
if items[index][0] <= weight:
newValue = items[index][1] + currentRow[weight - items[index][0]][1]
newWeight = items[index][0] + currentRow[weight - items[index][0]][0]
newCount = 1 + currentRow[weight - items[index][0]][2]
if newValue > oldElement[1]:
return (newWeight, newValue, newCount)
if newValue == oldElement[1]:
if newWeight < oldElement[0]:
return (newWeight, newValue, newCount)
elif newWeight == oldElement[0]:
if newCount <= oldElement[2]:
return (newWeight, newValue, newCount)
return oldElement
else:
return oldElement
def findItems_RepeatOFF(r, c):
'''
Use to find items combination via backtracking approach
'''
logging.info(f' ---< finding max value for weight {c} with items {items[1:r+1]} >---')
while True:
if items[r][0] <= c:
#if matrix[r][c] != 0:
if items[r][1] == Matrix_PossibleWays_RepeatOFF[r][c]:
selectedItems.append(item_positions[r])
logging.info(f' => {items[r]} Selected')
# No more items required
PossibleSack_RepeatOFF.append(selectedItems.copy())
selectedItems.pop()
logging.info(f' => {items[r]} Removed')
elif (Matrix_PossibleWays_RepeatOFF[r-1][c-items[r][0]] + items[r][1] == Matrix_PossibleWays_RepeatOFF[r][c]):
selectedItems.append(item_positions[r])
logging.info(f' => {items[r]} Selected')
# Serach for next suitable/pickable items
findItems_RepeatOFF(r-1, c-items[r][0])
selectedItems.pop()
logging.info(f' => {items[r]} Removed')
# else:
# return
if Matrix_PossibleWays_RepeatOFF[r-1][c] == Matrix_PossibleWays_RepeatOFF[r][c]:
r -= 1
else:
return
def findItems_RepeatON(r, c):
'''
Use to find items combination via backtracking approach (Repeatation is allowed)
'''
logging.info(f' ---< finding max value for weight {c} with items {items[1:r+1]} >---')
while True:
if items[r][0] <= c:
#if matrix[r][c] != 0:
if items[r][1] == Matrix_PossibleWays_RepeatON[r][c]:
selectedItems.append(item_positions[r])
logging.info(f' => {items[r]} Selected')
# No more items required
PossibleSack_RepeatON.append(selectedItems.copy())
selectedItems.pop()
logging.info(f' => {items[r]} Removed')
elif (Matrix_PossibleWays_RepeatON[r][c-items[r][0]] + items[r][1] == Matrix_PossibleWays_RepeatON[r][c]):
selectedItems.append(item_positions[r])
logging.info(f' => {items[r]} Selected')
# Serach for next suitable/pickable items
findItems_RepeatON(r, c-items[r][0])
selectedItems.pop()
logging.info(f' => {items[r]} Removed')
# else:
# return
if Matrix_PossibleWays_RepeatON[r-1][c] == Matrix_PossibleWays_RepeatON[r][c]:
r -= 1
else:
return
def findMinimalItems_RepeatOFF(r, c):
'''
find efficient items set required for solution (Repeatation of coins is not allowed)
efficient = Max value, Min Weight, Min items
'''
logging.info(f' ---< finding max value for weight {c} with items {items[1:r+1]} >---')
while True:
if items[r][0] <= c:
if (items[r][1] == Matrix_MinimalItems_RepeatOFF[r][c][1] and
items[r][0] == Matrix_MinimalItems_RepeatOFF[r][c][0]) :
selectedItems.append(item_positions[r])
logging.info(f' => {items[r]} Selected')
MinimalSack_RepeatOFF.append(selectedItems.copy())
selectedItems.pop()
logging.info(f' => {items[r]} Removed')
elif (Matrix_MinimalItems_RepeatOFF[r-1][c-items[r][0]][1] + items[r][1] == Matrix_MinimalItems_RepeatOFF[r][c][1] and
Matrix_MinimalItems_RepeatOFF[r-1][c-items[r][0]][0] + items[r][0] == Matrix_MinimalItems_RepeatOFF[r][c][0] and
Matrix_MinimalItems_RepeatOFF[r-1][c-items[r][0]][2] + 1 == Matrix_MinimalItems_RepeatOFF[r][c][2]) :
selectedItems.append(item_positions[r])
logging.info(f' => {items[r]} Selected')
findMinimalItems_RepeatOFF(r-1, c-items[r][0])
selectedItems.pop()
logging.info(f' => {items[r]} Removed')
if Matrix_MinimalItems_RepeatOFF[r-1][c] == Matrix_MinimalItems_RepeatOFF[r][c]:
r -= 1
else:
return
def findMinimalItems_RepeatON(r, c):
'''
find efficient items set required for solution (Repeatation of coins is allowed)
efficient = Max value, Min Weight, Min items
'''
logging.info(f' ---< finding max value for weight {c} with items {items[1:r+1]} >---')
while True:
if items[r][0] <= c:
if (items[r][1] == Matrix_MinimalItems_RepeatON[r][c][1] and
items[r][0] == Matrix_MinimalItems_RepeatON[r][c][0]) :
selectedItems.append(item_positions[r])
logging.info(f' => {items[r]} Selected')
MinimalSack_RepeatON.append(selectedItems.copy())
selectedItems.pop()
logging.info(f' => {items[r]} Removed')
elif (Matrix_MinimalItems_RepeatON[r][c-items[r][0]][1] + items[r][1] == Matrix_MinimalItems_RepeatON[r][c][1] and
Matrix_MinimalItems_RepeatON[r][c-items[r][0]][0] + items[r][0] == Matrix_MinimalItems_RepeatON[r][c][0] and
Matrix_MinimalItems_RepeatON[r][c-items[r][0]][2] + 1 == Matrix_MinimalItems_RepeatON[r][c][2]) :
selectedItems.append(item_positions[r])
logging.info(f' => {items[r]} Selected')
findMinimalItems_RepeatON(r, c-items[r][0])
selectedItems.pop()
logging.info(f' => {items[r]} Removed')
if Matrix_MinimalItems_RepeatON[r-1][c] == Matrix_MinimalItems_RepeatON[r][c]:
r -= 1
else:
return
def backTracking(option):
'''
Initiate backtracking to find items set
'''
if Cases.NonRepeat == option:
if totalValue:
findItems_RepeatOFF(N, M)
elif Cases.Repeat == option:
if totalValue:
findItems_RepeatON(N, M)
elif Cases.MinimalNonRepeat == option:
if totalValue:
findMinimalItems_RepeatOFF(N, M)
elif Cases.MinimalRepeat == option:
if totalValue:
findMinimalItems_RepeatON(N, M)
### Main Code ------------------------------------------------------------------------------------------------------------
showLogs = input('\nDo you wanna display logs (for tracking) ? { y/n } : ')
while showLogs not in ('y', 'Y', 'n', 'N'):
showLogs = input('invalid input ! try again : ')
if showLogs in ('y', 'Y'):
print('\n------------------------------------------------ Logs -----------------------------------------------------------------')
logging.basicConfig(level=logging.DEBUG)
else:
logging.disable(logging.CRITICAL)
logging.info('***Task Started*** \n')
logging.info('=> Fetching inputs ... ')
# Fetch User Inputs
## N -> no. of items, M -> max Weight that sack can hold
N, M = eval(input("\nEnter the number of items & max Weight for the knapsack problem (seperated by comma) : ").strip())[:2]
items_inputs = [
(0, 0),
*sorted(
enumerate(
[eval(input(f'Enter the item {i} Weight & Value (seperated by comma i.e w,v): ').strip())[:2] for i in range(1, N+1)],
1
),
key=lambda item: item[1][1]/item[1][0],
reverse=True
)
]
item_positions = list(map(lambda i: i[0], items_inputs)) # Get the original positions of items as per input from user
items = list(map(lambda i: i[1], items_inputs)) # items sorted according to most eligible first (greedy)
#print(items)
print('\nCases :- \n\t Possible -> give all the solution & \n\t Efficacious -> give solution such that Max value of sack with Min Weight & Min number of items')
while True:
while True:
try:
selectedCase = Cases(eval(input(f"\nSelect either case {{ {', '.join(list(map(lambda c: f'{c.name}({c.value})', Cases)))} }} : ")[0]))
break
except:
print('Please provide appropriate value from {1, 2, 3, 4}\n')
print(f'\n---- Mode -> {selectedCase.name} --- \n ')
logging.info('Matrix Calculations starterd ')
if selectedCase == Cases.NonRepeat:
prepareMatrix(matrix= Matrix_PossibleWays_RepeatOFF, memberFeeder= memberFeeder_PossibleWays_RepeatOFF)
solution = PossibleSack_RepeatOFF
totalValue = Matrix_PossibleWays_RepeatOFF[N][M]
elif selectedCase == Cases.Repeat:
prepareMatrix(matrix= Matrix_PossibleWays_RepeatON, memberFeeder= memberFeeder_PossibleWays_RepeatON, repeat= True)
solution = PossibleSack_RepeatON
totalValue = Matrix_PossibleWays_RepeatON[N][M]
elif selectedCase == Cases.MinimalNonRepeat:
prepareMatrix(matrix= Matrix_MinimalItems_RepeatOFF, memberFeeder= memberFeeder_MinimalItems_RepeatOFF)
solution = MinimalSack_RepeatOFF
totalValue = Matrix_MinimalItems_RepeatOFF[N][M][1]
elif selectedCase == Cases.MinimalRepeat:
prepareMatrix(matrix= Matrix_MinimalItems_RepeatON, memberFeeder= memberFeeder_MinimalItems_RepeatON, repeat= True)
solution = MinimalSack_RepeatON
totalValue = Matrix_MinimalItems_RepeatON[N][M][1]
logging.info('Matrix calculations completed')
logging.info('Backtracking Started --- ')
# backtracking
print('\nCalculating ...')
backTracking(selectedCase)
print('\nDone !')
logging.info('Backtracking completed ---')
if showLogs in ('y', 'Y'):
print('\n---------------------------------------------- Logs Over ---------------------------------------------------------------')
## Outputs --------------------------------------------------------------------
if totalValue:
print(f'\nMax Value that can be achieved after filling sack with {N} items & max capacity {M} weight is :- {totalValue}')
print("\nSolutions : \n")
for way in solution:
print(way)
cont = input('\n Want to explore more cases ?? (y/n) : ')
while cont not in ('y', 'Y', 'n', 'N'):
cont = input('invalid input ! try again : ')
if cont in ('n', 'N'):
break
Raw
KnapSack_V1.py
selectedItems = []
allSolutions = []
def findItems(r, c):
if c == 0 or r == 0:
if c == 0:
allSolutions.append(selectedItems.copy())
return
while True:
if items[r][0] <= c:
#if matrix[r][c] != 0:
if items[r][1] == matrix[r][c]:
selectedItems.append(r)
# No more items required
findItems(r-1, 0)
selectedItems.pop()
elif items[r][1] < matrix[r][c] and (matrix[r-1][c-items[r][0]] + items[r][1] == matrix[r][c]):
selectedItems.append(r)
# Serach for next suitable/pickable items
findItems(r-1, c-items[r][0])
selectedItems.pop()
# else:
# return
if matrix[r-1][c] == matrix[r][c]:
r -= 1
else:
return
# Fetch User Inputs
N, M = eval(input("Enter the number of items & max Weight for the knapsack problem (seperated by comma) : ").strip())[:2]
items = [
(0, 0),
*sorted(
[eval(input(f'Enter the item {i} Weight & Value (seperated by comma i.e w,v): ').strip())[:2] for i in range(1, N+1)],
key=lambda item: item[1]/item[0],
reverse=True
)
]
print(items, "\n")
matrix = []
for i in range(N+1):
row = []
for j in range(M+1):
if j == 0:
row.append(0)
elif i == 0:
row.append(0)
elif items[i][0] <= j:
leftWeight = j - items[i][0]
row.append(max(matrix[i-1][j], items[i][1] + matrix[i-1][leftWeight]))
else:
row.append(matrix[i-1][j])
matrix.append(row)
for row in matrix:
print(row)
if matrix[N][M] != 0:
findItems(N, M)
for ways in allSolutions:
print(ways)
# Backtracking
Raw
Notes
* KnapSack - DP Approach *
-------------------------
aim : To select items to fill Sack which can hold upto some max Weight
---
solution : 4 solution can be possible i.e
--------
1) Possible solutions : That include all possible combinations of items
- Repeatation of items allowed
- Repeatation of items not allowed
2) Efficacious solutions : Solution with max value, min weight, min items count for sack
(Minimum Weight & Minimum items are used)
- Repeatation of items allowed
- Repeatation of items not allowed
Example :
-------
maxWeight of Sack = 25
items (w,v): [(4,10), (8,20), (10,18), (20,30)] { w -> weight, v -> value }
1) Possible Solutions :
-> Repeatation Not ALlowed
value of sack after filling items : 48
selected items : [1,2,3]
-> Repeatation of coins allowed
value of sack after filling items : 60
selected items : [2,2,2] [2,2,1,1] [2,1,1,1,1] [1,1,1,1,1,1]
2) Efficacious Solution :
-> Repeatation Not ALlowed
value of sack after filling items : 48
selected items : [1,2,3]
-> Repeatation allowed
value of sack after filling items : 60
selected items : [2,2,2]
Approach : Bottom-Up Dynamic Programming
----------------------------------------
Logic Explanation :
________________
matrix -> m
row -> r ( items available at moment )
column -> c ( max weight of sack at moment )
1) Possible Solutions : ( Repeatation & Non-Repeatation have same fundamental logic with slight difference )
-> m[r][c] : gives the total(max) value of sack possible with the max weight (c) and using (r) items at moment
-> Base Case :
if 0 weight is demanded :- there is no way to fulfill it
if 0 items are available then there is no way to fulfill any weight value
Rest Case :
if item's weight at moment has value less than max weight of sack then we will check if after including this item if the max value of sack increase
than before
if yes then we will include that item
Note : Inclusion of item depends on Repeatation allowed or not,
if Repeatation allowed than we can have as number of quantity of item as we can for that amount
if repeatation not allowed then we can include item only once
2) Efficacious Solutions : ( Repeatation & Non-Repeatation Shares same fundamental logic with slight difference )
-> m[r][c] : gives the total(max) value of sack possible with the max weight (c) and using (r) items at moment with additional info
additional info : It also provides the min total weight of all item that can be included in sack at moment
It also procides the min item count that's required to be included in sack at moment
-> Base Case :
if 0 weight is demanded :- 0 items are required
if (0) no items are avilable then obviously min items required will be 0
Rest Case :
We have 2 option either select or reject the item : (let see how to take decision ) -
When to select :-
if after including current item : 1) max value of sack increases
2) total weight of sack is minimum
3) total number of items in sack is minimum
if any of above condition do not match then we will not include that item
Equations :
_________
item -> (w,v)
i -> row
j -> column ( max weight of sack )
vi -> value v of item at row i
wi -> weight w of item at row i
1) Possible Solutions :
Matrix element -> int value; v -> max value possible at moment
-> Repeatation Not allowed :-
m[i][j] = 0 j == 0
= 0 i == 0
= max(m[i-1][j], vi + m[i-1][j-wi]) wi <= j
= m[i-1][j] Rest all cases
-> Repeatation allowed :-
m[i][j] = 0 j == 0
= 0 i == 0
= max(m[i-1][j], vi + m[i][j-wi]) wi <= j
= m[i-1][j] Rest all cases
2) Efficacious Solutions :
Matrix element -> tuple t -> (w, v, c) => (min_weight, max_value, min_count) at moment
-> Repeatation Not allowed :-
new_v = vi + m[i-1][j-wi][1]
new_w = wi + m[i-1][j-wi][0]
new_c = 1 + m[i-1][j-wi][2]
old_v = m[i-1][j][1]
old_w = m[i-1][j][0]
old_c = m[i-1][j][2]
new_e = (new_w, new_v, new_c)
m[i][j] = 0 i or j == 0
if (new_v > old_v) wi <= j
new_e
if (new_v == old_v)
if (new_w < old_w)
new_e
if (new_w == old_w)
if (new_c <= old_c)
new_e
m[i-1][j]
m[i-1][j] Rest Case
-> Repeatation allowed :-
new_v = vi + m[i][j-wi][1]
new_w = wi + m[i][j-wi][0]
new_c = 1 + m[i][j-wi][2]
old_v = m[i-1][j][1]
old_w = m[i-1][j][0]
old_c = m[i-1][j][2]
new_e = (new_w, new_v, new_c)
m[i][j] = 0 i or j == 0
if (new_v > old_v) wi <= j
new_e
if (new_v == old_v)
if (new_w < old_w)
new_e
if (new_w == old_w)
if (new_c <= old_c)
new_e
m[i-1][j]
m[i-1][j] Rest Case
Example :
_______
Q item no: 1 2 3 4
items : [(2,8), (3,12), (4,10), (5,20)]
max weight of sack allowed: 6
1) Possible Solutions :
-> Repeatation not allowed :
Matrix :
j 0 1 2 3 4 5 6
wi vi i
0 0 0 [0, 0, 0, 0, 0, 0, 0 ]
2 8 1 [0, 0, 8, 8, 8, 8, 8 ]
3 12 2 [0, 0, 8, 12, 12, 20, 20]
5 20 3 [0, 0, 8, 12, 12, 20, 20]
4 10 4 [0, 0, 8, 12, 12, 20, 20]
Value of Sack :- 20
Possible Solutions : [4] [1,2] ( here item number represent the item from original set as of que )
-> Repeatation allowed :
Matrix :
j 0 1 2 3 4 5 6
wi vi i
0 0 0 [0, 0, 0, 0, 0, 0, 0 ]
2 8 1 [0, 0, 8, 8, 16, 16, 24]
3 12 2 [0, 0, 8, 12, 16, 20, 24]
5 20 3 [0, 0, 8, 12, 16, 20, 24]
4 10 4 [0, 0, 8, 12, 16, 20, 24]
Value of Sack :- 24
Possible Solutions : [2,2] [1,1,1]
2) Efficacious solutions :
-> Repeatation not allowed :
Matrix :
j 0 1 2 3 4 5 6
wi vi i
0 0 0 [(0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0)]
2 8 1 [(0, 0, 0), (0, 0, 0), (2, 8, 1), (2, 8, 1), (2, 8, 1), (2, 8, 1), (2, 8, 1)]
3 12 2 [(0, 0, 0), (0, 0, 0), (2, 8, 1), (3, 12, 1), (3, 12, 1), (5, 20, 2), (5, 20, 2)]
5 20 3 [(0, 0, 0), (0, 0, 0), (2, 8, 1), (3, 12, 1), (3, 12, 1), (5, 20, 1), (5, 20, 1)]
4 10 4 [(0, 0, 0), (0, 0, 0), (2, 8, 1), (3, 12, 1), (3, 12, 1), (5, 20, 1), (5, 20, 1)]
Value of Sack :- 20
Weight of Sack :- 5
number of items :- 1
Possible Solutions : [4]
-> Repeatation allowed:
Matrix :
j 0 1 2 3 4 5 6
wi vi i
0 0 0 [(0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0)]
2 8 1 [(0, 0, 0), (0, 0, 0), (2, 8, 1), (2, 8, 1), (4, 16, 2), (4, 16, 2), (6, 24, 3)]
3 12 2 [(0, 0, 0), (0, 0, 0), (2, 8, 1), (3, 12, 1), (4, 16, 2), (5, 20, 2), (6, 24, 2)]
5 20 3 [(0, 0, 0), (0, 0, 0), (2, 8, 1), (3, 12, 1), (4, 16, 2), (5, 20, 1), (6, 24, 2)]
4 10 4 [(0, 0, 0), (0, 0, 0), (2, 8, 1), (3, 12, 1), (4, 16, 2), (5, 20, 1), (6, 24, 2)]
Value of Sack :- 24
Weight of Sack :- 6
number of items :- 2
Possible Solutions : [2,2]
Backtracking :
____________
1) Possible Solutions :
if max Value is greater than 0 then :
-> Repeatation not allowed : (basic logic )
-----------------------
step 1) check if current item weight <= max weight of sack
i.e if vi <= j
step 2) then check if after selecting current item if required value is completely available then select current item & the set you get is final set
but if after including current item if remaining value is available with remaining weight from remaining items then include current item
otherwise go Up in row & look for current max Value
-> remaining items must be selected in such a way that total weight of remaining items must not exceed the (Current Max Weight - Current Item
Weight) &
at same time total value of remaining item must satisfy the (Current Max value - Current Item Val )
step 3) if in step 2 current element is selected then
go UP and look for j-wi weight i.e m[i-1][j-wi] <- seek for this
step 4) if step 1 is wrong then just go up & search again i.e r = r-1
REPEAT Step 1, 2 & 3, 4 until you get solution set in step 2
-> Repeatation allowed: (basic logic )
-------------------
step 1) check if current item weight <= max weight of sack
i.e if vi <= j
step 2) then check if after selecting current item if required value is completely satisfied then select current item & the set you get is final set
but if after including current item if total value is not satisfied then
check if remaining value is available with remaining weight from current items then include current item
otherwise go Up & look
-> items must be selected in such a way that total remaining weight must not exceed the (Current Max Weight - Current Item
Weight) &
at same time total remaining value must satisfy the (Current Max value - Current Item Val )
step 3) if in step 2 current element is selected then
look for j-wi weight in same row i.e m[i][j-wi] <- seek for this
step 4) if step 1 is wrong then just go up & search again i.e r = r-1
REPEAT Step 1, 2 & 3, 4 until you get solution set in step 2
| NOTE : above 2 method gives only 1 way out of many ways possible so inorder to get other ways, you need to repeat this method for all possible rows
where we can get the desired amount
2) Efficacious Solutions :
if max Value is greater than 0 then :
-> Repeatation not allowed : (basic logic )
-----------------------
steps 1) check if current item weight <= max weight of sack
i.e if vi <= j
step 2) then check if after selecting current item
if required value is completely satisfied
if required weight is completely satisfied
then select current item & the set you get is final set
Even if after selecting current item, max value is not fulfilled or min weight is not fulfilled:
then check if remaining value is available with remaining items
if remianing weight is available with remaining items
if item counts is fulfilled after accounting remaining elements inclusion
Otherwise look up in row for current maxValue with remaining elements
-> remaining item must selected in such a way that total weight of them must match the (Current Min Weight - Current Item Weight)
remaining item must selected in such a way that total value of them must match the (Current Max Value - Current Item Value)
remaining item must selected in such a way that total count of them must match the (Current Min Count - 1)
steps 3) if item in step 2 get's selected then Just go up &
look for j-wi weight in above row i.e m[i-1][j-wi] <- seek for this
step 4) if step 1 is wrong then just go up & search again i.e r = r-1
REPEAT Step 1, 2 & 3, 4 until you get solution set in step 2
-> Non-Repeatation Mode : (basic logic)
--------------------
steps 1) check if current item weight <= max weight of sack
i.e if vi <= j
step 2) then check if after selecting current item
if required value is completely satisfied
if required weight is completely satisfied
then select current item & the set you get is final set
Even if after selecting current item, max value is not fulfilled or min weight is not fulfilled:
then check if remaining value is available with current items
if remianing weight is available with current items
if item counts is fulfilled
Otherwise look up in row for current maxValue with remaining elements
-> item must selected in such a way that total weight of them must match the (Current Min Weight - Current Item Weight)
item must selected in such a way that total value of them must match the (Current Max Value - Current Item Value)
item must selected in such a way that total count of them must match the (Current Min Count - 1)
steps 3) if item in step 2 get's selected then Just
look for j-wi weight in same row i.e m[i][j-wi] <- seek for this
step 4) if step 1 is wrong then just go up & search again i.e r = r-1
REPEAT Step 1, 2 & 3, 4 until you get solution set in step 2
Raw
Test Cases ( sample )
Sample 1 :
-------
Input - 5, 20
[(2, 10), (7, 18), (15, 26), (5, 8), (13, 18)]
Repeat ON -> {100} [1,1,1,1,1,1,1,1,1,1]
Repeat Off -> {36} [5,4,1] [5,2] [1,2,4] [1,3]
MinRep ON -> {100} [1,1,1,1,1,1,1,1,1,1]
MinRep OFF -> {36} [1,2,4]
Sample 2 :
--------
Input - 4, 50
[(10, 20), (20, 40), (30, 50), (40, 50)]
Repeat OFF -> {90} [3, 2]
Repeat On -> {100} [2,2,1] [2,1,1,1] [1,1,1,1,1]
MinRep OFF -> {90} [3, 2]
MinRep ON -> {100} [2,2,1]
Sample 3
--------
Input - 4, 25
[(4,10), (8,20), (10,18), (20,30)]
Repeat Off -> {48} [1,2,3]
Repeat On -> {60} [2,2,2] [2,2,1,1] [2,1,1,1,1] [1,1,1,1,1,1]
MinRep Off -> {48} [1,2,3]
MinRep On -> {60} [2,2,2]
Sample 4
--------
Input - 4, 6
[(2,8), (3,12), (4,10), (5,20)]
Repeat OFF -> {20} [4] [2,1]
Repeat On -> {24} [2,2] [1,1,1]
MinRep OFF -> {20} [4]
MinRep On -> {24} [2,2]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment