[PYTHON] I think the limit of knapsack is not the weight but the volume w_11/22update
Good evening (* ´ω ｀) Thank you for your support m (_ _) m
I challenged the famous knapsack. While looking diagonally at the code of an expert I just considered what I wanted to do.
KnapSack.py
class Item:
def __init__(self,w=0,p=0):
self.weight=w
self.price=p
items = [ Item(300,400), Item(500,250), Item(200,980),
Item(600,340), Item(900,670), Item(1360,780),
Item(800,570), Item(250,800) ]
def knapsack(i, w):
if i==len(items):
return 0
if w - items[i].weight < 0.0:
return knapsack(i+1, w)
Val_sum0 = knapsack(i+1, w)
Val_sum1 = knapsack(i+1, w - items[i].weight) + items[i].price
return max(Val_sum0,Val_sum1)
p = knapsack(0, 1200)
print("MAXIMUM TOTAL PRICE is",p)
Whether you put your luggage or not Consider the number of attempts (number of attempts) as i. Fortunately, the items lined up are limited, It is a problem to find the maximum value within a given condition.
Let knapsack return 0 when trying to the end. Recursive promise, define this in the base case.
KnapSack.py
def knapsack(i, w):
if i==len(items):
return 0
However, this does not make the story, so In the process, we will add the price of the item.
Of course, it does not add infinitely. The maximum value must be found within the defined weight. Therefore, each time you add an item, subtract the item's weight from the defined maximum weight. When w --items [i] .weigh <0, I gave up adding items [i] because it exceeds the weight limit. Increment i to try to add the next item.
KnapSack.py
if w - items[i].weight < 0.0:
return knapsack(i+1, w)
Congratulations, as mentioned above
- Number of trials i is less than or equal to the number of items
- Never exceed the weight limit Only after clearing the conditions will you decide whether to add items or not. You can consider it.
KnapSack.py
Val_sum0 = knapsack(i+1, w)#Do not add
Val_sum1 = knapsack(i+1, w - items[i].weight) + items[i].price #to add
return max(Val_sum0,Val_sum1)#Which is bigger?
In the above description, I was addicted to Val_sum1 = knapsack (i + 1, w --items [i] .weight) + items [i] .price. Add items.price to knapsack? What? (ﾟ Д ﾟ) was.
But when you think about it, knapsack is a recursive process, so it eventually falls into the base case. That's right, it will be 0. Therefore, only the result of stacking items.price will be returned.
Then, since the above description is ** full search **, Duplicate calculations were included. I will reduce it.
However, it was possible, but it may be subtle (laughs)
knapsack.py
class Item:
def __init__(self,w=0,p=0):
self.weight=w
self.price=p
items = [ Item(300,400), Item(500,250), Item(200,980),
Item(600,340), Item(900,670), Item(1360,780),
Item(800,570), Item(250,800) ]
def knapsack(i, w):
if memo[i][w]:#Check if there is something in the corresponding cell of the memo.
return memo[i][w]#Return value when entered, calculation reduction!!
if i==len(items):
return 0
if w - items[i].weight < 0.0:
return knapsack(i+1, w)
Val_sum0 = knapsack(i+1, w)
Val_sum1 = knapsack(i+1, w - items[i].weight) + items[i].price
memo[i][w] = max(Val_sum0,Val_sum1) #Make a note!!
return memo[i][w]#Returns the value you wrote down
wgoal = 700
memo = [[[]for k in range(wgoal + 1)] for l in range(len(items)+1)] #Made a vast notepad(Lol)
p = knapsack(0,wgoal)
print("MAXIMUM TOTAL PRICE is",p)
What I've learned so far is to prepare notes and It is a challenge to reduce the calculation by calling what was calculated in the past.
However, the memo I prepared this time is too vast (laughs). What I'm writing down now is Make a note of the maximum price in terms of weight at a particular number of trials. If the weight is several hundred, the scale of the memo to be prepared will be large. Problem setting mistake !! (* noωno)
By the way, there is also a method that does not use recursion.
knap_dp.py
N = 8 #number of backs
w =[300, 500, 200, 600, 900, 1360, 800, 250]
v =[400, 250, 980, 340, 670, 780, 570, 800]
wgoal = 700
memo = [[0]*(wgoal+1)for l in range(N+1)]
for i in range(N):
for j in range(wgoal+1):
if j < w[i]:
memo[i+1][j] = memo[i][j]
else:
memo[i+1][j] = max(memo[i][j],memo[i][j-w[i]]+v[i])
print("MAXIMUM TOTAL PRICE is",memo[N][wgoal])
The outfit was very refreshing. I tried various weights with recursive processing, Switch to the for statement and on the i-th attempt I write down all the weights (it seems to be called DP).
I can't deny the feeling that I'm reading and writing, and somehow moving. Let's create an image with a little more local (* ´ 艸 ｀).
-11/22_update-------------------------------------------------------------
Reflecting on the problem setting mistake the other day, I changed it a little, easily (laughs)
knap_dp.py
N = 3 #number of backs
w =[3, 4, 5]
v =[30, 50, 60]
wgoal = 8
memo = [[0]*(wgoal+1)for l in range(N+1)]
for i in range(N):
for j in range(wgoal+1):
if j < w[i]:
memo[i+1][j] = memo[i][j]
else:
memo[i+1][j] = max(memo[i][j],memo[i][j-w[i]]+v[i])
print(f"i={i},j={j}")
for k in memo:
print(k)
print()
print("MAXIMUM TOTAL PRICE is",memo[N][wgoal])
I will execute it for the time being.
Execution result.py
i=0,j=0
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=1
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=2
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=3
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=4
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=5
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=6
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=7
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=0,j=8
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=0
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=1
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=2
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=3
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=4
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=5
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=6
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=7
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1,j=8
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=0
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=1
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=2
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2,j=3
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 0, 0, 0, 0, 0]
i=2,j=4
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 0, 0, 0, 0]
i=2,j=5
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 0, 0, 0]
i=2,j=6
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 0, 0]
i=2,j=7
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 80, 0]
i=2,j=8
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 30, 30, 30, 30, 30, 30]
[0, 0, 0, 30, 50, 50, 50, 80, 80]
[0, 0, 0, 30, 50, 60, 60, 80, 90]
MAXIMUM TOTAL PRICE is 90
A person who can be shown and understood this much is a genius.
I'm an ordinary person, so I'll organize it while creating an image.
First, imagine a memo you prepared yourself.
w is the weight. It will gradually increase toward wgoal.
Let's follow the program.
Let's go dong dong.
Now that we know what we want to do, we'll put together the rest of N = 0.
Let's try N = 1 with the same idea.
I will also try N = 2.
I see, 90 is the maximum.
I managed to follow the code, but
Do you make such a table in your head? Everyone is a genius (ﾟ Д ﾟ)
I practice little by little and go steadily (..) φ memo memo
Recommended Posts