数学建模社区-数学中国
标题:
python代码解决0-1背包问题
[打印本页]
作者:
2744557306
时间:
2023-11-7 11:17
标题:
python代码解决0-1背包问题
一、首先介绍一下0-1背包问题:
' }& z# p" m2 V$ Z% G! m1 L
0-1背包问题(0-1 Knapsack Problem)是一个经典的组合优化问题,通常在计算机科学和运筹学中讨论。这个问题涉及到一个背包和一组物品,每个物品都有一个特定的重量和价值。问题的目标是在给定背包的最大容量下,选择一组物品放入背包,以使得所选物品的总重量不超过背包的容量,同时最大化这些物品的总价值。
. V2 { A: Y& n* M
0-1背包问题的名称中的“0-1”表示每个物品要么完全放入背包(选择)要么完全不放入背包(不选择),不能部分放入。这是问题的一个关键特征,与分数背包问题不同,分数背包问题允许部分放入物品。
! j7 _) [7 Y6 k$ _7 u' M
问题的形式描述如下:
6 p- q! P3 L P! M2 V' k& M
1.给定一个固定容量的背包,通常表示为一个正整数W(背包的最大承载重量)。
L$ U9 Z1 S6 f' F p
2.给定一组物品,每个物品都有两个属性:重量(weight)和价值(value)。
+ ]4 w' }' p) h) a t0 L( Q! P
3.对每个物品,你可以选择将其放入背包(选择)或不放入背包(不选择)。
8 q; r; I9 z/ Z# K& U5 j2 c0 @
4.每个物品只能选择一次,即要么放入背包,要么不放入。
. l6 f: a- l$ Q+ y: T5 w+ o9 q
5.目标是选择一个物品组合,使得它们的总重量不超过背包容量W,同时使它们的总价值最大化。
0 F( C- f! p7 F: E+ N5 M3 D2 G
( a, i C# v$ p" r/ g
解决0-1背包问题的一种常见方法是使用动态规划(Dynamic Programming)算法。这个问题有广泛的应用,包括资源分配、排程问题、投资组合优化等领域。它还是计算复杂性理论中的一个经典问题,通常被用来说明NP难问题的概念。
7 \& ]) `2 K X0 l" Z1 b! ~$ u/ |
% ^7 b% _. N! j/ V
5 ?9 _9 o) `( i$ n7 h
二、 介绍代码
. [9 q6 _: S6 F2 O; @' k
这段代码是一个Python实现的0-1背包问题的解决方法,使用了动态规划算法来找到最优解。以下是对代码的详细解释:
def knapsack(v, w, n, capacity):
5 @$ i% t7 u& m. ^
i = 0
. x, o2 [; L$ c7 p6 o; h) P$ m4 t
capacity = capacity + 1 # 初始化背包容量最大值
$ _6 q& Z: J: A1 R6 v. c' {0 M1 T
m = np.zeros((n, capacity)) # 初始化
0 k3 N. ]5 g4 [6 u* Q' t
x = np.zeros(n)
复制代码
1.v 是一个长度为 n 的列表,表示每个物品的价值。
/ \: I4 P0 K1 j$ o. C
2.w 是一个长度为 n 的列表,表示每个物品的重量。
! x4 t+ J6 |4 _0 l$ P7 Z
3.n 表示物品的数量。
" h/ c' j: g, x! `# k
4.capacity 表示背包的容量。
5 ?, D) u+ T9 l7 V% Z
! ?& n4 w/ s2 L( w* Z
代码首先初始化了一个二维数组 m 作为动态规划表,其中 m
[j] 表示在考虑前 i 个物品时,背包容量为 j 时可以获得的最大总价值。数组 x 用来存储最终的解,x
表示是否选择第 i 个物品。
for i in range(n):
' g0 q) v9 z/ B2 v/ a
for j in range(capacity):
8 g4 h5 ~/ O" g8 K) i3 S
if (j >= w[i]):
" T3 N% n, |7 N" f4 v7 G3 m, I: B: k
m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])
" L$ x" {3 m9 \; Q
else:
( Q9 P* G; H' H; x
m[i][j] = m[i - 1][j]
复制代码
在这个部分,代码使用了一个嵌套的循环,遍历了所有物品和不同的背包容量。对于每个物品 i 和容量 j,代码计算了两种情况下的最大总价值:
- g1 X7 r$ T9 G- |5 e1 j; V
5.如果当前物品的重量 w
小于等于当前容量 j,那么可以选择将第 i 个物品放入背包,此时总价值为 m[i-1][j-w
] + v
,或者选择不放入,此时总价值为 m[i-1][j]。代码选择其中较大的值作为 m
[j]。
- Q5 V# I! r. O- @3 n) G O
6.如果当前物品的重量 w
大于当前容量 j,则无法放入物品,所以总价值等于上一行的值 m[i-1][j]。
4 Q/ r1 W1 c. v# N
7 M4 r0 c, ]5 M3 S( h; k2 D9 C
这个循环填充了动态规划表 m,最终 m[n-1][capacity] 包含了问题的最优解,即在给定容量下可以获得的最大总价值。
capacity = capacity - 1
6 a( Z" ]9 q* R7 t! c5 F5 n
for i in range(n - 1, 0, -1):
- x, ^: r; ]" f5 K
if (m[i][capacity] == m[i - 1][capacity]):
4 t$ Q$ x$ l2 @, b4 E) s }* Y. e
x[i] = 0
9 ^( `4 X7 A2 z% v& D6 E2 I
else:
4 M1 L' `+ B8 W/ o
x[i] = 1
- d! d. T/ u) H, y+ t" U( ]
capacity -= w[i]
0 |6 i9 H* _. E: C
x[0] = 1 if (m[1][capacity] > 0) else 0
复制代码
在这一部分,代码反向遍历动态规划表,从最后一行向前找到解的路径。如果 m
[capacity] 等于 m[i-1][capacity],表示第 i 个物品没有放入背包,否则放入背包,并更新剩余容量 capacity。
weight = 0
/ K8 ?- [5 T4 [3 m
value = 0
f" l, _) r$ c4 D7 T6 P$ P( U
print('装载的物品编号为:')
4 R' e) S$ v0 x; N
for i in range(len(x)):
: g8 B) D, S$ N( R
if (x[i] == 1):
6 X$ \, `/ S0 V5 b4 m; j# `( m
weight = weight + w[i]
% L) L0 r. l! r- H4 d) j3 M: m
value = value + v[i]
$ m* B) {: p. m" F' Y: X
print(' ', i + 1)
2 a3 }- [4 L% I" s" a, T
print('装载的物品重量为:')
" m7 x0 X/ O6 Y
print(weight)
: k i; V3 M! w8 \6 }) i- Q0 A1 ~7 i
print('装入的物品价值为:')
8 k! F, c* j2 }$ v) U8 Y
print(value)
( }% ^: Y- e& M6 M" t9 Y; {; a4 E
return m
复制代码
最后,代码计算了被选择的物品的总重量和总价值,并将它们打印出来。函数返回动态规划表 m。
6 F3 U& k# r6 Q/ d7 Q7 k
这段代码实现了0-1背包问题的解决方法,它通过动态规划算法找到最优解,即在给定背包容量下可以获得的最大总价值,以及选择哪些物品放入背包。
/ T4 Y2 A0 ?9 [6 i0 i
# Q i: V% {* b) M9 U2 u: k' \
最后在函数的输入文件中,如下例,第一行物品数量为:5 背包载重量为:10物品的重量列表为:[2, 2, 6, 5, 4] 物品的价值列表为: [6, 3, 5, 4, 6]
2 i! C4 r# b; t3 X& X5 A
2023-11-7 11:13 上传
下载附件
(8.27 KB)
, c! U' Y# o% t% m) ?* s2 r
9 x; \+ R8 i* E4 U, W9 L
接下来展示我们的输出结果:
8 Q- c# p/ Z" c+ z: R1 ^* E* Z
2023-11-7 11:16 上传
下载附件
(126.79 KB)
/ K+ _! ~+ u' |5 ]* S1 x: q
* k7 J3 J7 e$ F$ o) k$ r) d1 D3 l
$ M. g6 z/ k) _& ~+ K
具体代码如下:
* U6 H7 h8 Q# ?6 y0 b- p
4 z. M0 _ d' V( @
" O% Y& S/ z0 h# ~( w9 D5 A9 g: [3 n
1 p1 R" [3 I& [+ j. E# X2 }
0 J) W4 |0 x- t! ^, v3 @' h, D9 y" |
/ P" h/ g- g3 x: p9 o
基础0-1背包问题(动态规划).rar
2023-11-7 11:17 上传
点击文件名下载附件
下载积分: 体力 -2 点
3.58 KB, 下载次数: 0, 下载积分: 体力 -2 点
售价:
2 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5