QQ登录

只需要一步,快速开始

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

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

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

1192

主题

4

听众

2946

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2023-11-7 11:17 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
一、首先介绍一下0-1背包问题:
9 p- n" c6 Y% n7 ~) [# X# b7 k
        0-1背包问题(0-1 Knapsack Problem)是一个经典的组合优化问题,通常在计算机科学和运筹学中讨论。这个问题涉及到一个背包和一组物品,每个物品都有一个特定的重量和价值。问题的目标是在给定背包的最大容量下,选择一组物品放入背包,以使得所选物品的总重量不超过背包的容量,同时最大化这些物品的总价值。. Y7 y$ _& r6 [& N3 ?
         0-1背包问题的名称中的“0-1”表示每个物品要么完全放入背包(选择)要么完全不放入背包(不选择),不能部分放入。这是问题的一个关键特征,与分数背包问题不同,分数背包问题允许部分放入物品。
% S0 v; Q" i6 |; B
问题的形式描述如下:
3 B3 N9 l  c. ]: v; y
                 1.给定一个固定容量的背包,通常表示为一个正整数W(背包的最大承载重量)。
( N7 |7 k. b' k+ e9 B$ c& u/ y3 N                 2.给定一组物品,每个物品都有两个属性:重量(weight)和价值(value)。6 F7 t$ ]* {% N' Q! r
                 3.对每个物品,你可以选择将其放入背包(选择)或不放入背包(不选择)。
- O0 H, v& I7 I% P9 ~) ^. h. H3 }                 4.每个物品只能选择一次,即要么放入背包,要么不放入。
4 g' H9 b. T% r+ Y                 5.目标是选择一个物品组合,使得它们的总重量不超过背包容量W,同时使它们的总价值最大化。
  f  o  {8 h2 G
. w: D- T; w( t解决0-1背包问题的一种常见方法是使用动态规划(Dynamic Programming)算法。这个问题有广泛的应用,包括资源分配、排程问题、投资组合优化等领域。它还是计算复杂性理论中的一个经典问题,通常被用来说明NP难问题的概念。
$ t2 ~4 _! k  R$ O$ _
, j0 \' Y; D+ w8 K+ o) k% y6 s4 x; F8 @7 [
二、 介绍代码- ?6 @  w" q; q7 r
这段代码是一个Python实现的0-1背包问题的解决方法,使用了动态规划算法来找到最优解。以下是对代码的详细解释:
  1. def knapsack(v, w, n, capacity):! H2 _3 ^9 ?8 i& L: y
  2.     i = 0
    # _: }$ L. k# U5 u, l  t  e
  3.     capacity = capacity + 1  # 初始化背包容量最大值- K# `7 Z  j% O/ `* A
  4.     m = np.zeros((n, capacity))  # 初始化5 k# n/ Q% I1 N( s
  5.     x = np.zeros(n)
复制代码
1.v 是一个长度为 n 的列表,表示每个物品的价值。7 ^5 U$ c) q: b" E! Z& i
2.w 是一个长度为 n 的列表,表示每个物品的重量。
1 }6 m. d/ J4 E. i( K  x3.n 表示物品的数量。
! u, z: @/ ~) G% J: s5 j* w& Q4.capacity 表示背包的容量。
; O/ p, h- c8 L" a5 B6 g% [) k( P" V  S) s8 y; B1 I
代码首先初始化了一个二维数组 m 作为动态规划表,其中 m[j] 表示在考虑前 i 个物品时,背包容量为 j 时可以获得的最大总价值。数组 x 用来存储最终的解,x 表示是否选择第 i 个物品。
  1.     for i in range(n):
    # f5 G* `$ j7 p* E, R% A2 \
  2.         for j in range(capacity):- S! K  @9 x4 z: j! f4 ]6 f
  3.             if (j >= w[i]):) T+ T* Z  s9 `\" i+ e( T
  4.                 m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])
    , K* W, D: n+ m* a
  5.             else:
    8 b: x- J. P* d3 L5 q
  6.                 m[i][j] = m[i - 1][j]
复制代码
在这个部分,代码使用了一个嵌套的循环,遍历了所有物品和不同的背包容量。对于每个物品 i 和容量 j,代码计算了两种情况下的最大总价值:
0 e1 y  D) O$ ~5.如果当前物品的重量 w 小于等于当前容量 j,那么可以选择将第 i 个物品放入背包,此时总价值为 m[i-1][j-w] + v,或者选择不放入,此时总价值为 m[i-1][j]。代码选择其中较大的值作为 m[j]。/ g6 ]& d" A. H2 c! O
6.如果当前物品的重量 w 大于当前容量 j,则无法放入物品,所以总价值等于上一行的值 m[i-1][j]。) I" V! L2 T  i4 _9 @
$ R# A+ e; L4 m) j7 R' Y$ U
这个循环填充了动态规划表 m,最终 m[n-1][capacity] 包含了问题的最优解,即在给定容量下可以获得的最大总价值。
  1.     capacity = capacity - 1
    * @+ W. K5 J) F) I- i) Y9 [
  2.     for i in range(n - 1, 0, -1):
      ^3 R& H( @, Z; B
  3.         if (m[i][capacity] == m[i - 1][capacity]):* h7 t  p# [- M: Z$ R4 A
  4.             x[i] = 0# M- H# n/ D7 {% t% Z
  5.         else:4 O! a1 U$ Y+ A
  6.             x[i] = 1& R\" s% v( `) z3 ^7 U5 c: P; X
  7.             capacity -= w[i]
    4 l; K6 i+ ~; q- D& l) N; n7 e
  8.     x[0] = 1 if (m[1][capacity] > 0) else 0
复制代码
在这一部分,代码反向遍历动态规划表,从最后一行向前找到解的路径。如果 m[capacity] 等于 m[i-1][capacity],表示第 i 个物品没有放入背包,否则放入背包,并更新剩余容量 capacity。
  1.     weight = 0: P3 v  y- o6 W( y
  2.     value = 0
    & H\" r- v0 I3 z: N
  3.     print('装载的物品编号为:')  B6 h/ J6 |: p; I/ S
  4.     for i in range(len(x)):
    # P, E7 I, C( }% H2 m
  5.         if (x[i] == 1):
    0 l6 Q$ N% }' c
  6.             weight = weight + w[i]$ y8 J  `9 r  G7 w: K% d3 b$ y
  7.             value = value + v[i]
    - B9 x: C: |! k/ j# }9 q! w
  8.             print(' ', i + 1)( M9 I7 ?& t5 I/ ~
  9.     print('装载的物品重量为:')! Y1 K, [$ E9 N8 s( @
  10.     print(weight). i) C7 ^+ P& ]3 e6 u1 X6 V
  11.     print('装入的物品价值为:'), \( h1 P7 Y3 m$ U+ Y3 d
  12.     print(value)
    4 w4 s1 u$ r0 d. ]/ I$ D: U
  13.     return m
复制代码
最后,代码计算了被选择的物品的总重量和总价值,并将它们打印出来。函数返回动态规划表 m。, g9 J* e( X, M: S) T0 w
这段代码实现了0-1背包问题的解决方法,它通过动态规划算法找到最优解,即在给定背包容量下可以获得的最大总价值,以及选择哪些物品放入背包。
" @1 m+ I- z8 U' b& D
) W% R% y0 t2 b: T& Z最后在函数的输入文件中,如下例,第一行物品数量为:5 背包载重量为:10物品的重量列表为:[2, 2, 6, 5, 4] 物品的价值列表为: [6, 3, 5, 4, 6], S  ~( X* Z5 n! T& l5 f9 P
VeryCapture_20231107110045.jpg
1 R& w' v& C8 S" I8 J( Y
8 O( {( q0 T3 \* n1 b. G8 R
接下来展示我们的输出结果:

  J# f) ?4 W3 I) e' X
VeryCapture_20231107110508.jpg

+ y4 n, {1 i/ Z( r" x/ |- H
2 M+ t( J  e) }" \7 e
6 l% x' w8 ~+ w
具体代码如下:

% E5 w+ T% |4 h
; T6 z( ?! b! c5 R) N$ j4 t% F( u  \3 E& F$ q6 o

% e$ @! t3 z: K/ {5 A* d

- D. F7 ^. f7 q7 J4 }* h( |3 g* |  y3 G( M% ^+ e- i3 D

基础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-8-26 06:36 , Processed in 0.747134 second(s), 55 queries .

回顶部