背包问题之模板题 Python实现

2022/6/15 1:22:32

本文主要是介绍背包问题之模板题 Python实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言

01背包——万恶之源
我一定要搞好这个背包问题!

一、 01背包

1. 问题描述

01背包问题:给定\(N\)个物品和容量为\(V\)的背包,每个物品有两个属性:价值\(w_i\)和体积\(v_i\),每个物品只能取1次,问在背包中放入哪些物品可以使得总价值最大?

输入例子:

4 5 # 物品数量和背包容量
1 2 # 物品1的体积和价值
2 4
3 4
4 5

输出例子:

8 # 价值最大的结果

2. 解题思路

  1. 状态表示f[i, j](一般背包问题都是二维)
  • 表示所有选法,满足只从前i个物品中选,并且选出来的物品总体积小于等于j,f[i, j]的值为这些选法的价值的最大值
    • 前i个物品:这个价值最大值从前i个物品考虑,并不代表前i个物品都选了
  • 最后答案是\(f[N][V]\)
  1. 状态计算
  • 对于f[i, j],可以将该集合划分为两部分:选法包含i,选法不包含i。两部分的最大值就是f[i, j]

  • 如何计算这两部分

    • 选法不包含i:从1~i-1中选,且总体积不超过j的所有选法的最大值(这些选法一定不会包含i),即f[i-1, j]

    • 选法包含i:包含i的选法的最大值

      如何求?——“曲线救国”

      1. 先不去看第i个物品,即从第1~i-1个物品中选。

        但是由于最后要加上第i个物品,所以在第1到i-1个物品选时,选法不能超过\(j - v[i]\),得出这部分最大值,即\(f[i-1, j - v[i]]\)

      2. 再加上第i个物品的价值,即可得到包含i的选法的最大价值

        即\(f[i-1, j - v[i]] + w[i]\)

  • 注意,当\(j < v_i\)的时候,即选法总体积装不下第i个物品的时候,选法包含i这个情况不存在



这篇关于背包问题之模板题 Python实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程