- 在线时间
- 480 小时
- 最后登录
- 2026-6-1
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7823 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2934
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1174
- 主题
- 1189
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
一、首先介绍一下0-1背包问题:' P4 j- j+ s2 s/ R7 L
0-1背包问题(0-1 Knapsack Problem)是一个经典的组合优化问题,通常在计算机科学和运筹学中讨论。这个问题涉及到一个背包和一组物品,每个物品都有一个特定的重量和价值。问题的目标是在给定背包的最大容量下,选择一组物品放入背包,以使得所选物品的总重量不超过背包的容量,同时最大化这些物品的总价值。. }0 w6 p; S( g; }" Z, n+ @
0-1背包问题的名称中的“0-1”表示每个物品要么完全放入背包(选择)要么完全不放入背包(不选择),不能部分放入。这是问题的一个关键特征,与分数背包问题不同,分数背包问题允许部分放入物品。
2 A1 d/ C2 y/ v/ g7 d! D- A" c$ u问题的形式描述如下: 9 L: e; t9 w. h2 v$ m
1.给定一个固定容量的背包,通常表示为一个正整数W(背包的最大承载重量)。
! H F+ v e9 l 2.给定一组物品,每个物品都有两个属性:重量(weight)和价值(value)。
4 |5 D, ^7 @5 R8 H6 r9 O# p0 v2 Z 3.对每个物品,你可以选择将其放入背包(选择)或不放入背包(不选择)。* P1 z- |, j/ L; s [) {
4.每个物品只能选择一次,即要么放入背包,要么不放入。9 g' n1 i. @# h& J
5.目标是选择一个物品组合,使得它们的总重量不超过背包容量W,同时使它们的总价值最大化。
/ P. [! O0 @2 u$ s4 z0 a) h
0 B. p4 l& d- A$ Z o# ?% }解决0-1背包问题的一种常见方法是使用动态规划(Dynamic Programming)算法。这个问题有广泛的应用,包括资源分配、排程问题、投资组合优化等领域。它还是计算复杂性理论中的一个经典问题,通常被用来说明NP难问题的概念。
; l5 Q4 T: D' z8 q, H$ M* A$ U& M- S( a* ]: j3 o K# f
9 x) ~5 T: e7 T1 O. r6 i) m% K
二、 介绍代码
# S* O$ ~, S4 p4 Q3 V# M% O( E9 c2 f* z这段代码是一个Python实现的0-1背包问题的解决方法,使用了动态规划算法来找到最优解。以下是对代码的详细解释:- def knapsack(v, w, n, capacity):3 q$ `- e2 E& U; T\" M
- i = 0
6 O; M1 ^% M% z\" S - capacity = capacity + 1 # 初始化背包容量最大值1 q% M0 m4 [\" Q! d% D2 H4 S' K
- m = np.zeros((n, capacity)) # 初始化
8 _+ d2 t: h\" h4 B* I - x = np.zeros(n)
复制代码 1.v 是一个长度为 n 的列表,表示每个物品的价值。
: M( W) n' n# B" P9 l3 Q2.w 是一个长度为 n 的列表,表示每个物品的重量。1 U: z3 ?6 z" }2 [+ [' W& _$ ]
3.n 表示物品的数量。
3 s6 a; U' H, A9 W( G3 c D) V4.capacity 表示背包的容量。
& m+ l8 G0 y% N9 O g' L7 ]" h* d5 t
代码首先初始化了一个二维数组 m 作为动态规划表,其中 m[j] 表示在考虑前 i 个物品时,背包容量为 j 时可以获得的最大总价值。数组 x 用来存储最终的解,x 表示是否选择第 i 个物品。- for i in range(n):3 E/ ?$ @( Q2 J- _. V. q
- for j in range(capacity):
1 q9 B7 c) ?' R) i. {# T\" R3 p( N - if (j >= w[i]):
' @2 _( c, [+ k\" H - m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])
r; G9 a g8 L - else:
8 V6 N/ p+ _; ~% e0 L ~ - m[i][j] = m[i - 1][j]
复制代码 在这个部分,代码使用了一个嵌套的循环,遍历了所有物品和不同的背包容量。对于每个物品 i 和容量 j,代码计算了两种情况下的最大总价值:
/ ~4 N3 A/ K B q+ `5.如果当前物品的重量 w 小于等于当前容量 j,那么可以选择将第 i 个物品放入背包,此时总价值为 m[i-1][j-w] + v,或者选择不放入,此时总价值为 m[i-1][j]。代码选择其中较大的值作为 m[j]。
8 Z4 _4 n6 E0 I5 k* ^7 S7 u+ H6 |6.如果当前物品的重量 w 大于当前容量 j,则无法放入物品,所以总价值等于上一行的值 m[i-1][j]。
9 i' j- u0 f# |* I o; R
! _- W8 _. r/ W2 I' z; P3 G# K这个循环填充了动态规划表 m,最终 m[n-1][capacity] 包含了问题的最优解,即在给定容量下可以获得的最大总价值。- capacity = capacity - 10 K8 d% o7 B, S5 i
- for i in range(n - 1, 0, -1):
8 M$ h0 R! c' I\" N - if (m[i][capacity] == m[i - 1][capacity]):
2 X2 q! ?& ?. N - x[i] = 0
9 Q- D3 P0 l8 r- J$ W - else:: l; k) N- S y( T% r* u
- x[i] = 1
: Q. T! z% E& w0 v\" @3 v% W - capacity -= w[i]' q9 L( h! r/ Z9 ^3 U U; h: [
- x[0] = 1 if (m[1][capacity] > 0) else 0
复制代码 在这一部分,代码反向遍历动态规划表,从最后一行向前找到解的路径。如果 m[capacity] 等于 m[i-1][capacity],表示第 i 个物品没有放入背包,否则放入背包,并更新剩余容量 capacity。- weight = 0! ~$ S0 f0 j3 m% @
- value = 0
- S4 U# d, a2 m1 I) e8 W - print('装载的物品编号为:')- f8 g4 e( {# Y; p: k- T/ p; H2 T; ~
- for i in range(len(x)):+ \( I6 b0 M' P4 J, r$ v0 x; T
- if (x[i] == 1):
2 M0 y- R( R6 a7 O+ \* j/ w( L! }+ h - weight = weight + w[i]5 I- D/ ^: P: i! F/ @7 E' x
- value = value + v[i]
' P4 M2 e, k; }! {, n - print(' ', i + 1)1 a\" F( ~7 U& {3 X- p
- print('装载的物品重量为:')2 V& l/ L0 E y3 l7 L+ N: z9 z5 E- x
- print(weight): Y4 h3 Q- ]6 \ k7 ~: ?2 b
- print('装入的物品价值为:')
1 V8 K1 Y% a0 r8 C y$ E0 {5 z - print(value)
6 o& y. {. f2 ]1 D7 p - return m
复制代码 最后,代码计算了被选择的物品的总重量和总价值,并将它们打印出来。函数返回动态规划表 m。: n" w7 @/ e. Z: Z) r- f8 w& L
这段代码实现了0-1背包问题的解决方法,它通过动态规划算法找到最优解,即在给定背包容量下可以获得的最大总价值,以及选择哪些物品放入背包。
1 {8 D: e$ X; m- D- e3 f2 z
* x S k. G' c/ J最后在函数的输入文件中,如下例,第一行物品数量为:5 背包载重量为:10物品的重量列表为:[2, 2, 6, 5, 4] 物品的价值列表为: [6, 3, 5, 4, 6]
5 H6 y( j. I) {! p* z+ L. ]" K1 T: U3 V2 n. V9 }, u+ c
& ]2 f2 d( c9 V7 L) {2 {
接下来展示我们的输出结果: 3 M! q |2 O; f0 i' ?
4 Q. k$ u' N$ S B, a" V5 h$ Z$ W. q0 F& @8 i) e
9 Y$ f Q2 ^6 `' t6 t) N
具体代码如下: . n# r8 Y0 O5 b/ J! W
/ K* \" [: }" T( C% u3 ?
' ~6 ?, F8 h8 s% L* ?- g& t0 B/ v' H1 j: x+ G: q0 x9 f
0 t2 r* u3 V+ R- R
4 j! g4 k4 i0 h$ }. C% X
|
zan
|