数学建模社区-数学中国
标题:
python代码解决0-1背包问题
[打印本页]
作者:
2744557306
时间:
2023-11-7 11:17
标题:
python代码解决0-1背包问题
一、首先介绍一下0-1背包问题:
; F* W( ]/ N: L
0-1背包问题(0-1 Knapsack Problem)是一个经典的组合优化问题,通常在计算机科学和运筹学中讨论。这个问题涉及到一个背包和一组物品,每个物品都有一个特定的重量和价值。问题的目标是在给定背包的最大容量下,选择一组物品放入背包,以使得所选物品的总重量不超过背包的容量,同时最大化这些物品的总价值。
" w2 J% q5 J5 b) c& w. E2 \, ]
0-1背包问题的名称中的“0-1”表示每个物品要么完全放入背包(选择)要么完全不放入背包(不选择),不能部分放入。这是问题的一个关键特征,与分数背包问题不同,分数背包问题允许部分放入物品。
8 j0 L5 f' v2 M1 A2 Z" b
问题的形式描述如下:
: {9 k0 _& x6 Y4 d
1.给定一个固定容量的背包,通常表示为一个正整数W(背包的最大承载重量)。
& J$ I3 ^) N; g$ G$ m' E7 G
2.给定一组物品,每个物品都有两个属性:重量(weight)和价值(value)。
/ G7 O( P& l" L. j: ~6 A6 @( a: r
3.对每个物品,你可以选择将其放入背包(选择)或不放入背包(不选择)。
1 _' A: W/ `0 {6 W, f
4.每个物品只能选择一次,即要么放入背包,要么不放入。
1 N& G2 L0 v# h9 H
5.目标是选择一个物品组合,使得它们的总重量不超过背包容量W,同时使它们的总价值最大化。
, K2 V! r" z1 ] L" `" J0 ]
) |$ A U6 ^5 m
解决0-1背包问题的一种常见方法是使用动态规划(Dynamic Programming)算法。这个问题有广泛的应用,包括资源分配、排程问题、投资组合优化等领域。它还是计算复杂性理论中的一个经典问题,通常被用来说明NP难问题的概念。
: z. {5 f% w: x; r$ I( C" v
: W% r' p# J' }' U2 k2 c" K8 j* _
9 Z5 J7 t9 g& a# p. L! [- `
二、 介绍代码
! m+ l' B$ g# W& k2 `7 G
这段代码是一个Python实现的0-1背包问题的解决方法,使用了动态规划算法来找到最优解。以下是对代码的详细解释:
def knapsack(v, w, n, capacity):
; T. R0 H3 B( X- k* F
i = 0
3 L) H2 I2 u( G. ^/ F: O/ Q) r
capacity = capacity + 1 # 初始化背包容量最大值
2 S4 s0 I, { v( @( u
m = np.zeros((n, capacity)) # 初始化
9 Q6 ^. G9 z7 O( d
x = np.zeros(n)
复制代码
1.v 是一个长度为 n 的列表,表示每个物品的价值。
& y% A/ B! W& e+ X5 N( M) V% M
2.w 是一个长度为 n 的列表,表示每个物品的重量。
. s! Y& Q. {6 y6 L9 O1 ^: q
3.n 表示物品的数量。
7 h# U _% x5 c! l' T6 T- N, X$ F
4.capacity 表示背包的容量。
3 q. f) `% \' N4 W1 S+ J; c
+ t6 `8 s* [! h7 M( K# \6 t$ ? O
代码首先初始化了一个二维数组 m 作为动态规划表,其中 m
[j] 表示在考虑前 i 个物品时,背包容量为 j 时可以获得的最大总价值。数组 x 用来存储最终的解,x
表示是否选择第 i 个物品。
for i in range(n):
t5 P/ q$ r5 r9 Z E& \: P5 [
for j in range(capacity):
. T- e( Y% K7 ~- H0 U( ?6 D8 @* V
if (j >= w[i]):
& \$ G( h! ]: X+ J& f$ \
m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])
- A/ M2 ~8 M- G1 ]* d
else:
N4 R2 h* H, |+ R
m[i][j] = m[i - 1][j]
复制代码
在这个部分,代码使用了一个嵌套的循环,遍历了所有物品和不同的背包容量。对于每个物品 i 和容量 j,代码计算了两种情况下的最大总价值:
2 k$ {# \, R k2 }/ {4 F
5.如果当前物品的重量 w
小于等于当前容量 j,那么可以选择将第 i 个物品放入背包,此时总价值为 m[i-1][j-w
] + v
,或者选择不放入,此时总价值为 m[i-1][j]。代码选择其中较大的值作为 m
[j]。
* ~: X4 @7 m( c! e3 _6 X3 U% J
6.如果当前物品的重量 w
大于当前容量 j,则无法放入物品,所以总价值等于上一行的值 m[i-1][j]。
6 D5 D) @7 J# w; H1 Y
, d) \3 F' ^3 {2 x0 N
这个循环填充了动态规划表 m,最终 m[n-1][capacity] 包含了问题的最优解,即在给定容量下可以获得的最大总价值。
capacity = capacity - 1
$ R- x- H* u6 l2 l
for i in range(n - 1, 0, -1):
7 d" P' v+ J- X1 P
if (m[i][capacity] == m[i - 1][capacity]):
" `7 @4 e' N' \6 Z
x[i] = 0
9 s: D0 C; y. G- L& O
else:
* H6 _. l/ b& s, ]$ g8 S
x[i] = 1
B# h) `* c( m, P
capacity -= w[i]
% L7 q/ N N5 {9 c* l+ ^7 c% z; P
x[0] = 1 if (m[1][capacity] > 0) else 0
复制代码
在这一部分,代码反向遍历动态规划表,从最后一行向前找到解的路径。如果 m
[capacity] 等于 m[i-1][capacity],表示第 i 个物品没有放入背包,否则放入背包,并更新剩余容量 capacity。
weight = 0
& S4 n/ M" l' v: ]3 Y
value = 0
! e2 U- S. C) _8 k
print('装载的物品编号为:')
9 P8 m9 {& a+ ^
for i in range(len(x)):
. R) P' Y% D) G4 K3 J
if (x[i] == 1):
" g. G: Q) A+ T) p
weight = weight + w[i]
( e% I9 x5 n: }' ~8 p5 u( c
value = value + v[i]
- [9 g4 G5 L3 W
print(' ', i + 1)
* `2 C! ?8 E0 ?
print('装载的物品重量为:')
: l& s4 Z4 @/ x! H k2 w& i
print(weight)
3 a: \! e1 H& l9 v
print('装入的物品价值为:')
% O- C/ ]/ U4 J" ~' z% {: N
print(value)
6 L1 D% H) g F3 N% R5 M
return m
复制代码
最后,代码计算了被选择的物品的总重量和总价值,并将它们打印出来。函数返回动态规划表 m。
; V- F" Y4 A; {- ^
这段代码实现了0-1背包问题的解决方法,它通过动态规划算法找到最优解,即在给定背包容量下可以获得的最大总价值,以及选择哪些物品放入背包。
: t: N+ h8 V$ h" M2 H
/ u# n. z8 u0 m, @. F: _9 B
最后在函数的输入文件中,如下例,第一行物品数量为:5 背包载重量为:10物品的重量列表为:[2, 2, 6, 5, 4] 物品的价值列表为: [6, 3, 5, 4, 6]
0 j! B8 Y5 s( Y8 z+ Y3 h2 m, N
2023-11-7 11:13 上传
下载附件
(8.27 KB)
" |% r, U, e7 }4 h( H* V- E- u' _
U! s9 F- X! n# c, r& l
接下来展示我们的输出结果:
$ h" f- j( K- g% D
2023-11-7 11:16 上传
下载附件
(126.79 KB)
I$ h: F/ a; D" o' t5 B
- x' z5 K' [$ u
; k3 Y* P; J- i- r
具体代码如下:
9 ^' W# y2 N! C5 H2 v1 h
0 o+ U4 O0 x! I8 B. I3 b
+ z. d( M* F2 R, }
' O) |4 e7 v& W1 ?0 a+ |5 D. _
! u% G- h6 \( ?/ T
8 y. r! x& {7 I+ b9 q) V) O m* f
基础0-1背包问题(动态规划).rar
2023-11-7 11:17 上传
点击文件名下载附件
下载积分: 体力 -2 点
3.58 KB, 下载次数: 0, 下载积分: 体力 -2 点
售价:
2 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5