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

  1. Number of trials i is less than or equal to the number of items
  2. 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. 図1.PNG Let's follow the program. 図2.PNG Let's go dong dong. 図3.PNG 図4.PNG 図5.PNG 図6.PNG Now that we know what we want to do, we'll put together the rest of N = 0. 図7.PNG Let's try N = 1 with the same idea. 図8.PNG I will also try N = 2. 図9.PNG 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

I think the limit of knapsack is not the weight but the volume w_11/22update
I checked the contents of docker volume
The Python project template I think of.
The update of conda is not finished.
The value of pyTorch torch.var () is not distributed
When you think the update of ManjaroLinux is strange
I know, but I can't stop--Python is a collection of common mistakes
I made AI think about the lyrics of Kenshi Yonezu (pre-processing)
I tried to expand the size of the logical volume with LVM
I made AI think about the lyrics of Kenshi Yonezu (implementation)
If the accuracy of the PCR test is poor, why not repeat the test?
I want to display the number of num_boost_rounds when early_stopping is applied using XGBoost callback (not achieved)