- 在线时间
- 481 小时
- 最后登录
- 2026-8-25
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7859 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2946
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1177
- 主题
- 1192
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
一、首先介绍一下0-1背包问题:
' j5 `' A+ R3 d7 W' w* k6 { 0-1背包问题(0-1 Knapsack Problem)是一个经典的组合优化问题,通常在计算机科学和运筹学中讨论。这个问题涉及到一个背包和一组物品,每个物品都有一个特定的重量和价值。问题的目标是在给定背包的最大容量下,选择一组物品放入背包,以使得所选物品的总重量不超过背包的容量,同时最大化这些物品的总价值。+ x% Q( p$ P9 r- n
0-1背包问题的名称中的“0-1”表示每个物品要么完全放入背包(选择)要么完全不放入背包(不选择),不能部分放入。这是问题的一个关键特征,与分数背包问题不同,分数背包问题允许部分放入物品。
+ j2 r' W% n: E7 |) ]问题的形式描述如下:
" g& i8 }$ i7 }% K 1.给定一个固定容量的背包,通常表示为一个正整数W(背包的最大承载重量)。3 S, j) W# Y8 P: w. u( n
2.给定一组物品,每个物品都有两个属性:重量(weight)和价值(value)。
$ R7 R* J2 f/ j- U2 X/ } 3.对每个物品,你可以选择将其放入背包(选择)或不放入背包(不选择)。
4 }4 K8 n; R. `& d 4.每个物品只能选择一次,即要么放入背包,要么不放入。
. R$ E5 s, C$ n& L* V/ ? 5.目标是选择一个物品组合,使得它们的总重量不超过背包容量W,同时使它们的总价值最大化。
) L; Y4 h% i5 I" N7 {: d8 I
: d5 t5 e9 W6 p Q6 C解决0-1背包问题的一种常见方法是使用动态规划(Dynamic Programming)算法。这个问题有广泛的应用,包括资源分配、排程问题、投资组合优化等领域。它还是计算复杂性理论中的一个经典问题,通常被用来说明NP难问题的概念。$ ` D) E4 C5 f( x5 Q% X- a
! e# Y& A" W3 m4 p3 s2 M9 `! G; {6 k- @2 f, I# W9 y5 l
二、 介绍代码$ c9 W( T8 m& \; ?' o, n
这段代码是一个Python实现的0-1背包问题的解决方法,使用了动态规划算法来找到最优解。以下是对代码的详细解释:- def knapsack(v, w, n, capacity):
/ S9 w% g7 q& G. s - i = 0, F1 u\" F2 J# X; `1 I$ b\" T% ?; g
- capacity = capacity + 1 # 初始化背包容量最大值
* a+ Y+ G0 P: w) T6 h, v - m = np.zeros((n, capacity)) # 初始化5 H& H/ Z2 O; ~# t
- x = np.zeros(n)
复制代码 1.v 是一个长度为 n 的列表,表示每个物品的价值。4 J; @, n: r6 X& F
2.w 是一个长度为 n 的列表,表示每个物品的重量。0 P# z1 J7 e7 C- J4 D9 Q! o7 H! E
3.n 表示物品的数量。9 u9 C! K$ d' x! M
4.capacity 表示背包的容量。. `5 \5 p8 l- v* j8 j. T& A5 f& k7 W9 j
% @2 }+ Z" O) r- W代码首先初始化了一个二维数组 m 作为动态规划表,其中 m[j] 表示在考虑前 i 个物品时,背包容量为 j 时可以获得的最大总价值。数组 x 用来存储最终的解,x 表示是否选择第 i 个物品。- for i in range(n):6 D6 r/ `' ~9 e: T
- for j in range(capacity):
. G' V% P$ k# g, l7 l - if (j >= w[i]):, E8 M\" ^, O\" N7 h( \, K7 O; D
- m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])0 D5 b0 G, M/ C; s/ J\" D5 U
- else:3 |5 g% [+ v+ Z! O Y: {
- m[i][j] = m[i - 1][j]
复制代码 在这个部分,代码使用了一个嵌套的循环,遍历了所有物品和不同的背包容量。对于每个物品 i 和容量 j,代码计算了两种情况下的最大总价值:$ [9 L! e5 H( N8 Q
5.如果当前物品的重量 w 小于等于当前容量 j,那么可以选择将第 i 个物品放入背包,此时总价值为 m[i-1][j-w] + v,或者选择不放入,此时总价值为 m[i-1][j]。代码选择其中较大的值作为 m[j]。7 U4 |" i7 W5 _3 o3 a
6.如果当前物品的重量 w 大于当前容量 j,则无法放入物品,所以总价值等于上一行的值 m[i-1][j]。
1 l" b: q( { Z/ {) e8 e4 W. J' `/ z x
这个循环填充了动态规划表 m,最终 m[n-1][capacity] 包含了问题的最优解,即在给定容量下可以获得的最大总价值。- capacity = capacity - 12 F' A' a% g5 d- S/ f\" q8 w
- for i in range(n - 1, 0, -1):
L3 I1 c$ N5 p: c8 \ - if (m[i][capacity] == m[i - 1][capacity]):
' C4 y: Z. J! p8 @0 S. O - x[i] = 0
' {: F6 t# {# p( B - else:
\" ^\" l4 m. h5 J - x[i] = 1/ K* ]6 r6 X% X2 ~1 g P
- capacity -= w[i]
1 d0 E' w8 e: x7 A - x[0] = 1 if (m[1][capacity] > 0) else 0
复制代码 在这一部分,代码反向遍历动态规划表,从最后一行向前找到解的路径。如果 m[capacity] 等于 m[i-1][capacity],表示第 i 个物品没有放入背包,否则放入背包,并更新剩余容量 capacity。- weight = 0: H. m n8 V* N$ ^9 U. q
- value = 0
b K& y; \9 L( Q+ P& d. ^ - print('装载的物品编号为:')
5 \# A$ W# I$ n4 A - for i in range(len(x)):
( I6 `: k8 @9 l$ C# [8 y& k* x - if (x[i] == 1):& |3 B+ H' C+ `$ m0 c$ w% K1 T) F
- weight = weight + w[i]8 [1 q* ^8 v; `\" N+ |
- value = value + v[i]7 L! |7 _1 F0 x9 B7 B R\" k
- print(' ', i + 1)
; {: X! s4 o% C6 t1 F - print('装载的物品重量为:')- k, v! b5 K ] [# w; q
- print(weight)
/ w% Y, d# f- c/ \1 I - print('装入的物品价值为:')7 z9 Y# o5 ~5 a' D$ }$ ?( ?
- print(value)8 Q* \( F& u1 ^5 x7 w. V6 \$ g
- return m
复制代码 最后,代码计算了被选择的物品的总重量和总价值,并将它们打印出来。函数返回动态规划表 m。
0 F, m$ e3 }2 N1 P这段代码实现了0-1背包问题的解决方法,它通过动态规划算法找到最优解,即在给定背包容量下可以获得的最大总价值,以及选择哪些物品放入背包。
( u! r$ d/ m7 B1 D* I8 ~( Z2 ]' ?: H# Y, P# m8 {; { f
最后在函数的输入文件中,如下例,第一行物品数量为:5 背包载重量为:10物品的重量列表为:[2, 2, 6, 5, 4] 物品的价值列表为: [6, 3, 5, 4, 6]
/ H1 { A: x: p: ^* W
1 I" B% z, D" D% ]* [+ X/ `6 J y3 j/ v& e8 e8 u0 K6 o4 k3 X" W7 x
接下来展示我们的输出结果:
3 C- ~- b& ~' M# {
" b) Z7 ~& h) U0 x I5 c' ^
4 Y# A) p; j8 f! S! @; Y4 ^, X
( I. c+ \/ k$ T) D具体代码如下: ! Z7 S1 s& @* \2 q2 j3 G8 H W
5 @: r, Q' D4 B) \3 h, X. l+ C5 C. H
* Q2 c# {6 m, O3 _+ N8 s7 n
: T1 w: D1 ?+ {8 S7 d1 }. w" {5 h! Y" Q) @! g
4 q" u2 ]6 {7 |" }7 f |
zan
|