[Python] Dynamic programming knapsack problem

AOJ Knapsack Problem

Unlimited number of knapsack problems

There are $ N $ types of items that weigh $ v_i $ and weigh $ w_i $, and knapsacks that weigh $ W $.

Select the item and put it in the knapsack so that the following conditions are met:

When applying to an optimization problem, in general, the following two problems must be met:

Find the maximum total value.

Solving the problem

The external design by dynamic programming is as follows.

Definition of $ dp [i + 1] [j] $: The maximum value of the total value when the total weight is selected to be $ j $ or less from the items up to the $ i $ question.

dp initial condition:

dp[0][j]=1

Definition of dp recurrence formula:

dp[i+1][j]=max\{dp[i][j-k×w[i]]+k×v[i] \}

This would result in a triple loop, so the amount of calculation would be $ O (nW ^ 2) $, which is time over. By transforming the recurrence formula, the loop of $ k $ can be eliminated and the amount of calculation can be $ O (nW) $. This variant is intended to eliminate duplicate calculations in information processing. The way to understand is to find $ dp [i + 1] [j] $, not from $ dp [i] [*] $, which is one step before, but $ dp [i] [j] $ and $ dp [ It's enough to look at i + 1] [jw [i]] + v [i] $, and vice versa. The explanation of the ant book is easy to understand.

Transformation of dp recurrence formula:

dp[i+1][j]=max(dp[i][j], dp[i+1][j-w[i]]+v[i])

Solution: $ dp [n] [W] $

Sample code


n = int(input())
w = []
v = []
for i in range(n):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
W = int(input())

dp = [[0] * (W + 1) for i in range(n + 1)]

for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])

print(dp[n][W])

Recommended Posts

[Python] Dynamic programming knapsack problem
[Python] Dynamic programming ABC015D
[Python] Dynamic programming TDPC D
[Python] Dynamic programming TDPC A
Animate the basics of dynamic programming and the knapsack problem
Python programming note
Knapsack problem memorandum
Python dynamic typing
Programming in python
Studying dynamic programming ①
Learn dynamic programming in Python (A ~ E)
Solving the Python knapsack problem with the greedy algorithm
3. 3. AI programming with Python
Competitive programming diary python 20201213
Python programming with Atom
Competitive programming diary python 20201220
Competitive programming with python
Programming problem "4 Queen Square"
Python programming in Excel
LEGO Mindstorms 51515 Python Programming
Competitive programming diary python
Programming problem collection (Q31-Q35)
Programming with Python Flask
Programming with Python and Tkinter
[Python] Technique to reduce dimensions with DP (Dynamic Programming) [AtCoder]
Python3 programming functions personal summary
ABC163 C problem with python3
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Atcoder Acing Programming Contest Python
Python Selenium Dynamic download wait
Python web programming article summary
Paiza Python Primer 1 Learn Programming
Programming problem collection (Q16 to Q20)
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Python Competitive Programming Site Summary
Python Machine Learning Programming> Keywords
ambisonics simulation (external problem) Python
Python Programming Workshop-Super Introductory Vol.4
[Python] Find Fibonacci numbers at high speed (memoization, dynamic programming)
Memoization recursion and dynamic programming known by Python Fibonacci sequence
An introduction to Python Programming
Python # Snap7 Libray Import problem
ABC188 C problem with python3
Network programming with Python Scapy
ABC187 C problem with python
Programming problem collection (Q11 to Q15)
Solve the Python knapsack problem with a branch and bound method
[Swift / Ruby / Python / Java] Object-oriented programming
Python3 standard input for competitive programming
Functional programming in Python Project Euler 1
[Note] Project Euler in Python (Problem 1-22)
[Introduction to Python3 Day 1] Programming and Python
Functional programming in Python Project Euler 3
[Python] [Table of Contents Links] Python Programming
Dynamic proxy with python, ruby, PHP
[Python] Object-oriented programming learned with Pokemon
ABC166 in Python A ~ C problem
Easy Python + OpenCV programming with Canopy
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (034-038 Dynamic programming: Knapsack DP basic)
Reinforcement learning 3 Dynamic programming / TD method