数学建模社区-数学中国
标题:
python代码解决0-1背包问题
[打印本页]
作者:
2744557306
时间:
2023-11-7 11:17
标题:
python代码解决0-1背包问题
一、首先介绍一下0-1背包问题:
2 X$ r1 W+ z9 N3 X+ ~- \. J+ d
0-1背包问题(0-1 Knapsack Problem)是一个经典的组合优化问题,通常在计算机科学和运筹学中讨论。这个问题涉及到一个背包和一组物品,每个物品都有一个特定的重量和价值。问题的目标是在给定背包的最大容量下,选择一组物品放入背包,以使得所选物品的总重量不超过背包的容量,同时最大化这些物品的总价值。
1 I: D' @8 q% M# Z3 H" m
0-1背包问题的名称中的“0-1”表示每个物品要么完全放入背包(选择)要么完全不放入背包(不选择),不能部分放入。这是问题的一个关键特征,与分数背包问题不同,分数背包问题允许部分放入物品。
7 v$ x- q' @5 \( |
问题的形式描述如下:
+ f1 |4 ^- U; M' X: e
1.给定一个固定容量的背包,通常表示为一个正整数W(背包的最大承载重量)。
7 q1 A( d g7 @4 d
2.给定一组物品,每个物品都有两个属性:重量(weight)和价值(value)。
( N9 @. C* A- H% F" G
3.对每个物品,你可以选择将其放入背包(选择)或不放入背包(不选择)。
% g) N( b6 `1 M
4.每个物品只能选择一次,即要么放入背包,要么不放入。
+ ^ ?4 b# P# H" W) h7 @, h
5.目标是选择一个物品组合,使得它们的总重量不超过背包容量W,同时使它们的总价值最大化。
$ `! N" N; F( |+ ^* O6 W
( r! ]6 ]# e$ j! U
解决0-1背包问题的一种常见方法是使用动态规划(Dynamic Programming)算法。这个问题有广泛的应用,包括资源分配、排程问题、投资组合优化等领域。它还是计算复杂性理论中的一个经典问题,通常被用来说明NP难问题的概念。
1 o; n$ R* x" y; ]4 l
' y% ]2 N; u% V4 ~
" A2 g& F, |) X- E
二、 介绍代码
7 f; e, l# M# w& s4 n; d) o8 j
这段代码是一个Python实现的0-1背包问题的解决方法,使用了动态规划算法来找到最优解。以下是对代码的详细解释:
def knapsack(v, w, n, capacity):
- y& v" x, B& C9 L R( u
i = 0
- A1 N! _# |9 C) q/ @" r1 l
capacity = capacity + 1 # 初始化背包容量最大值
& D/ P% [$ Z! }( m5 l& a5 o+ p( E$ E
m = np.zeros((n, capacity)) # 初始化
. \7 J: P- D- y" Y; s! J! t
x = np.zeros(n)
复制代码
1.v 是一个长度为 n 的列表,表示每个物品的价值。
1 _5 O7 Y' n; [4 k; W' E
2.w 是一个长度为 n 的列表,表示每个物品的重量。
5 ? H. S( |, Y' |
3.n 表示物品的数量。
# I) K4 I, a! V# T* G/ _ G: f
4.capacity 表示背包的容量。
- \" T. s& Z2 ?7 `; ^1 _) C$ a8 J2 B
. `: d6 E2 S/ U
代码首先初始化了一个二维数组 m 作为动态规划表,其中 m
[j] 表示在考虑前 i 个物品时,背包容量为 j 时可以获得的最大总价值。数组 x 用来存储最终的解,x
表示是否选择第 i 个物品。
for i in range(n):
% Z! I; d3 W' s
for j in range(capacity):
1 m6 k% ~+ [7 v4 H7 e! {; g
if (j >= w[i]):
! v9 N5 X; m: u! s% j9 {* D
m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])
; j# v" D3 G9 v* y+ F& ~5 W: p
else:
. ]( L9 C, c! m6 N4 V4 W
m[i][j] = m[i - 1][j]
复制代码
在这个部分,代码使用了一个嵌套的循环,遍历了所有物品和不同的背包容量。对于每个物品 i 和容量 j,代码计算了两种情况下的最大总价值:
4 R. y9 `+ J& j
5.如果当前物品的重量 w
小于等于当前容量 j,那么可以选择将第 i 个物品放入背包,此时总价值为 m[i-1][j-w
] + v
,或者选择不放入,此时总价值为 m[i-1][j]。代码选择其中较大的值作为 m
[j]。
& ^* ~; Q5 B0 _" R7 N
6.如果当前物品的重量 w
大于当前容量 j,则无法放入物品,所以总价值等于上一行的值 m[i-1][j]。
6 E$ F9 I2 r7 G. N8 M+ ^
1 N" W4 e# W% k* G) A. E" q; H
这个循环填充了动态规划表 m,最终 m[n-1][capacity] 包含了问题的最优解,即在给定容量下可以获得的最大总价值。
capacity = capacity - 1
5 {+ v1 n( t `' e5 L2 c ~; N
for i in range(n - 1, 0, -1):
7 @/ p7 b7 D0 Z- @
if (m[i][capacity] == m[i - 1][capacity]):
. B; R, O* n2 D- u) ~+ k
x[i] = 0
& i" I& K3 M3 u" P- G5 {" _
else:
# b$ p: C5 ? T9 ^! |4 J2 J
x[i] = 1
- E" ]" X$ j4 Q
capacity -= w[i]
3 Z9 I) T/ h8 I# U: _$ X. x
x[0] = 1 if (m[1][capacity] > 0) else 0
复制代码
在这一部分,代码反向遍历动态规划表,从最后一行向前找到解的路径。如果 m
[capacity] 等于 m[i-1][capacity],表示第 i 个物品没有放入背包,否则放入背包,并更新剩余容量 capacity。
weight = 0
0 F1 r- o9 g' k( J8 D' @
value = 0
- _4 ?1 {. z" K
print('装载的物品编号为:')
^% ?6 j# V: r" U& h
for i in range(len(x)):
0 F0 h: R- L3 ^5 _- c( W2 B8 z
if (x[i] == 1):
/ I c4 p" a* ~! y# L/ ]
weight = weight + w[i]
7 w1 ~8 \4 u4 M3 R
value = value + v[i]
: O+ V6 V4 g- N" l) ~1 s! r- Z
print(' ', i + 1)
- f! T& `4 l# G! @: B3 J
print('装载的物品重量为:')
# M$ d4 h) I( Y3 x, g3 K$ @2 u
print(weight)
1 U$ H6 ~: a e, N3 G% Y
print('装入的物品价值为:')
# g8 J8 u6 o" o+ a- G
print(value)
_# X1 x" I3 d9 u
return m
复制代码
最后,代码计算了被选择的物品的总重量和总价值,并将它们打印出来。函数返回动态规划表 m。
# P) |1 h" F8 |
这段代码实现了0-1背包问题的解决方法,它通过动态规划算法找到最优解,即在给定背包容量下可以获得的最大总价值,以及选择哪些物品放入背包。
# Y$ w. P( I& f
5 @& r7 }8 M2 T9 I+ X- N
最后在函数的输入文件中,如下例,第一行物品数量为:5 背包载重量为:10物品的重量列表为:[2, 2, 6, 5, 4] 物品的价值列表为: [6, 3, 5, 4, 6]
4 ^6 y7 b1 T, z- i/ [$ g" M
2023-11-7 11:13 上传
下载附件
(8.27 KB)
! z% f% \% R, |$ ~. u% s5 G8 e+ N
' ~. F: ^8 R, y2 ^
接下来展示我们的输出结果:
6 o/ O$ O" p( l* } G0 M' \+ f
2023-11-7 11:16 上传
下载附件
(126.79 KB)
0 p* |3 |; E$ @$ b, O
) b. h! m# z5 K8 k4 N$ z( v. l
7 Y6 G8 i ?- D9 _
具体代码如下:
4 J7 f6 i: }) T, p& j
3 P3 A7 |3 ?+ D$ c- G8 s G
/ F$ R8 Q" `+ J3 z( C; ]" g' d
: b1 U: f% H! U; ^: H
" D2 D/ R1 P, {! l9 g
+ R6 C/ d0 h8 F. q) c5 E% r
基础0-1背包问题(动态规划).rar
2023-11-7 11:17 上传
点击文件名下载附件
下载积分: 体力 -2 点
3.58 KB, 下载次数: 0, 下载积分: 体力 -2 点
售价:
2 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5