QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2677|回复: 0
打印 上一主题 下一主题

python代码解决0-1背包问题

[复制链接]
字体大小: 正常 放大

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2023-11-7 11:17 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
一、首先介绍一下0-1背包问题:. c0 X+ ]$ E" D- E# ?) N3 J$ m2 j
        0-1背包问题(0-1 Knapsack Problem)是一个经典的组合优化问题,通常在计算机科学和运筹学中讨论。这个问题涉及到一个背包和一组物品,每个物品都有一个特定的重量和价值。问题的目标是在给定背包的最大容量下,选择一组物品放入背包,以使得所选物品的总重量不超过背包的容量,同时最大化这些物品的总价值。
0 s6 f( J: V% j         0-1背包问题的名称中的“0-1”表示每个物品要么完全放入背包(选择)要么完全不放入背包(不选择),不能部分放入。这是问题的一个关键特征,与分数背包问题不同,分数背包问题允许部分放入物品。' S4 n9 n8 C$ a/ _
问题的形式描述如下:

9 Z. j( ~3 ?4 A2 y& F, U                 1.给定一个固定容量的背包,通常表示为一个正整数W(背包的最大承载重量)。
+ p& @. z' ^) p- d+ g                 2.给定一组物品,每个物品都有两个属性:重量(weight)和价值(value)。
$ S5 ?: V& C; K' X& Q7 }  N( k* p                 3.对每个物品,你可以选择将其放入背包(选择)或不放入背包(不选择)。
/ [( ~  Q6 `: o9 W                 4.每个物品只能选择一次,即要么放入背包,要么不放入。
1 ~4 \8 t: j% o: f                 5.目标是选择一个物品组合,使得它们的总重量不超过背包容量W,同时使它们的总价值最大化。: T8 @$ |- a0 w0 c/ l
/ P( W- `6 o* R, R
解决0-1背包问题的一种常见方法是使用动态规划(Dynamic Programming)算法。这个问题有广泛的应用,包括资源分配、排程问题、投资组合优化等领域。它还是计算复杂性理论中的一个经典问题,通常被用来说明NP难问题的概念。
! D5 y4 q0 ]9 i( i- e
3 Q, ]2 g0 d* W" p( L# m! k1 O0 z2 k  F
二、 介绍代码
5 _7 N& e6 `1 e6 B$ E5 _$ a- j这段代码是一个Python实现的0-1背包问题的解决方法,使用了动态规划算法来找到最优解。以下是对代码的详细解释:
  1. def knapsack(v, w, n, capacity):
    - E$ W6 ?: y, e# ]& o+ R
  2.     i = 0' C& I: f  o$ H4 F
  3.     capacity = capacity + 1  # 初始化背包容量最大值
    / z\" K  \5 s2 P, Q! m, ^
  4.     m = np.zeros((n, capacity))  # 初始化! d: i' y( o5 ^2 X' i4 b' H4 {
  5.     x = np.zeros(n)
复制代码
1.v 是一个长度为 n 的列表,表示每个物品的价值。# {+ _+ p0 R- X2 x0 a; ~& X8 a
2.w 是一个长度为 n 的列表,表示每个物品的重量。
* t& ^6 a: J- ]1 T3.n 表示物品的数量。
9 {1 y8 v0 F6 i4.capacity 表示背包的容量。
- ~2 V$ }8 s. y6 l. X
& U6 Y, J9 Y& Y# ]. z代码首先初始化了一个二维数组 m 作为动态规划表,其中 m[j] 表示在考虑前 i 个物品时,背包容量为 j 时可以获得的最大总价值。数组 x 用来存储最终的解,x 表示是否选择第 i 个物品。
  1.     for i in range(n):
    8 K# E, I5 N4 d) j2 ]% b! d9 W8 W
  2.         for j in range(capacity):
    \" X) l( n: Y6 L; z# l: i+ N4 e' O
  3.             if (j >= w[i]):% X. {, W& R& W: N) ^4 G
  4.                 m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])9 e0 ~\" d) {) V$ w3 _) U
  5.             else:7 m# Y6 L8 S& ~6 f
  6.                 m[i][j] = m[i - 1][j]
复制代码
在这个部分,代码使用了一个嵌套的循环,遍历了所有物品和不同的背包容量。对于每个物品 i 和容量 j,代码计算了两种情况下的最大总价值:) s; j% L9 x* q$ }3 w
5.如果当前物品的重量 w 小于等于当前容量 j,那么可以选择将第 i 个物品放入背包,此时总价值为 m[i-1][j-w] + v,或者选择不放入,此时总价值为 m[i-1][j]。代码选择其中较大的值作为 m[j]。
. D2 x9 `! p' Y0 R6.如果当前物品的重量 w 大于当前容量 j,则无法放入物品,所以总价值等于上一行的值 m[i-1][j]。) e! N5 v" e; B) v( |

. z5 x7 l4 k* Y& x+ ^: m; p这个循环填充了动态规划表 m,最终 m[n-1][capacity] 包含了问题的最优解,即在给定容量下可以获得的最大总价值。
  1.     capacity = capacity - 16 x- P7 c7 z: G* h; r5 t' ?% u
  2.     for i in range(n - 1, 0, -1):
    + r: q1 n; e) n% ^4 |
  3.         if (m[i][capacity] == m[i - 1][capacity]):
    + |% X) A, d3 f# x\" U% B; z
  4.             x[i] = 0
    3 l, T7 M' J\" `* y$ Y, [
  5.         else:
    ( z, A# E2 C. C1 ~
  6.             x[i] = 1% X. W! L. ]! v  k
  7.             capacity -= w[i]
    8 N# E$ P0 I$ o) f/ z( h
  8.     x[0] = 1 if (m[1][capacity] > 0) else 0
复制代码
在这一部分,代码反向遍历动态规划表,从最后一行向前找到解的路径。如果 m[capacity] 等于 m[i-1][capacity],表示第 i 个物品没有放入背包,否则放入背包,并更新剩余容量 capacity。
  1.     weight = 0
    ( O, E/ x# P4 M) u! D- ~
  2.     value = 06 q2 G9 p+ x# y& L( a
  3.     print('装载的物品编号为:')
    $ {: Y1 K0 f) A0 Y) G  n+ F
  4.     for i in range(len(x)):+ q; E$ y/ I% b- v5 d+ G* b! g
  5.         if (x[i] == 1):, q5 ^4 T% B3 C8 l
  6.             weight = weight + w[i]/ _7 l1 [8 S- U7 y8 G- ^
  7.             value = value + v[i]
    : M7 A8 D7 ^# C
  8.             print(' ', i + 1)( ?\" f  T. D  j+ z
  9.     print('装载的物品重量为:')
    / A% V- V2 @\" J+ x
  10.     print(weight)
    ! ?$ _$ n* o9 W9 A' o8 w( h
  11.     print('装入的物品价值为:')
    : B: S1 h' u5 D  k( O. d
  12.     print(value): N) ]8 X8 t: E/ P2 G* }# a
  13.     return m
复制代码
最后,代码计算了被选择的物品的总重量和总价值,并将它们打印出来。函数返回动态规划表 m。' ]& z! Q4 {6 U
这段代码实现了0-1背包问题的解决方法,它通过动态规划算法找到最优解,即在给定背包容量下可以获得的最大总价值,以及选择哪些物品放入背包。
+ t8 }2 k. L6 i1 X, `5 l* }- {6 K$ d+ U" Y
最后在函数的输入文件中,如下例,第一行物品数量为:5 背包载重量为:10物品的重量列表为:[2, 2, 6, 5, 4] 物品的价值列表为: [6, 3, 5, 4, 6]
6 N3 D+ p/ P: Q6 J, B' v4 a: S2 N
VeryCapture_20231107110045.jpg

% w! o) J# E  O+ X- O! q9 a0 q. j' u5 M1 W( s  s* ]) v
接下来展示我们的输出结果:
5 Y0 p/ M  k6 `: ?1 J0 T
VeryCapture_20231107110508.jpg

4 t5 z4 w, z$ T+ R7 o
$ U0 [' x' m9 S1 T

! ~+ @! U  K& O. J& i
具体代码如下:
& k% V+ |: I, J: I, m9 A6 B
& o2 [# @8 p3 f

9 E9 Y6 g2 B% q4 ~: ^6 j1 m/ ?" ^  c
$ ^  R1 E# B) n
8 ]( K7 J$ Y/ S/ ]8 n
6 R6 L# Q2 k+ V( [

基础0-1背包问题(动态规划).rar

3.58 KB, 下载次数: 0, 下载积分: 体力 -2 点

售价: 2 点体力  [记录]  [购买]

zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-6-5 13:17 , Processed in 1.261329 second(s), 55 queries .

回顶部