背包问题九讲

数据结构背包问题背景介绍：数据结构是计算机科学中非常重要的一门学科，它研究的是数据组织、存储和管理的方式。

背包问题是数据结构中的一个经典问题，它涉及到在给定的一组物品中选择一些物品放入背包中，使得背包的总重量或总价值达到最大化。

在本文中，我们将详细介绍背包问题的定义、解决方法和应用领域。

一、问题定义背包问题可以被描述为：给定一个背包，它能容纳一定的重量，再给定一组物品，每个物品有自己的重量和价值。

我们的目标是找到一种方式将物品放入背包中，使得背包的总重量不超过其容量，同时背包中物品的总价值最大化。

二、解决方法1. 贪心算法贪心算法是一种简单而有效的解决背包问题的方法。

它基于贪心的思想，每次选择当前具有最大价值重量比的物品放入背包中。

具体步骤如下：- 计算每个物品的价值重量比，即物品的价值除以其重量。

- 按照价值重量比从大到小对物品进行排序。

- 依次将物品放入背包中，直到背包的总重量达到容量限制或所有物品都放入背包。

贪心算法的优点是简单快速，但它并不能保证一定能找到最优解。

2. 动态规划动态规划是解决背包问题的一种经典方法。

它将问题划分为若干子问题，并通过求解子问题的最优解来求解原问题的最优解。

具体步骤如下：- 定义一个二维数组dp，其中dp[i][j]表示在前i个物品中，背包容量为j时的最大价值。

- 初始化dp数组的第一行和第一列为0，表示背包容量为0或物品数量为0时的最大价值都为0。

- 逐行填充dp数组，对于每个物品，考虑将其放入背包或不放入背包两种情况，选择价值最大的方案更新dp数组。

- 最终dp数组的最后一个元素dp[n][m]即为问题的最优解，其中n为物品数量，m为背包容量。

动态规划方法能够保证找到最优解，但其时间复杂度较高，对于大规模的问题可能会耗费较长的计算时间。

三、应用领域背包问题在实际生活和工程领域中有着广泛的应用，以下是一些常见的应用领域：1. 物流配送在物流配送中，背包问题可以用来优化货车的装载方案，使得货车的装载量最大化，从而减少运输成本。

此模型解决的是运输工具包括卫星的最优装载问题。 其数学模型为：
1
设 xi为第 i 种物品装入的件数，则背包问题可归结为如下
形式的整数规划模型：
n
∑ max z = gi (xi ) i =1
∑ n
i=1
ai xi
≤
a
xi ≥ 0
整数 （i = 1,2,L, n)
下面从一个例子来分析动态规划建模。
9.3 背 包 问 题
一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为a (千克)，现有n种物品可供他选择装入 背包。第i种物品的单位重量为 ai (千克)，其价值（可以是表
明本物品对登山者的重要性指标）是携带数量 xi 的函数
gi ( xi )（i=1，2，…n）.问旅行者应如何选择携带物品的件 数，以使总价值最大？
x1
+ 4x2 + 5x3 ≤ xi ≥ 0, 整数
10
(i = 1,2,3)
5x3
s3 = s4 − 5x3 货物3
s4 = 10
g1 ( x1 ) = 4 x1
g2(x2 ) = 5x2
g3(x3) = 6x3
K=2 时 其中
f2 (s3)
=
max {g
0≤4 x2 ≤s3
2
(
x2
)
+
f1(s2 )}
3
x1
+ 4x2 + 5x3 ≤ xi ≥ 0, 整数
10
(i = 1,2,3)
5x3 s3 = s4 − 5x3
货物3
s4 = 10
g1 ( x1 ) = 4 x1
g2(x2 ) = 5x2

f[n][m]即为最优解。
【参考程序】
#include<cstdio> using namespace std;
const int maxm = 201, maxn = 31;
int m, n;
int w[maxn], c[maxn];
int f[maxn][maxm];
int main()
{
scanf("%d%d",&m, &n);
for (int i=1; i <= n; i++)
//设f(v)表示重量不超过v公斤的最大价值
for (int v = m; v >= w[i]; v--)
if (f[v-w[i]]+c[i]>f[v])
f[v] = f[v-w[i]]+c[i];
printf("%d",f[m]);
// f(m)为最优解
【例9-12】、完全背包问题 【问题描述】
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限 的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品 可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
【输入格式】
第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)； 第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。 【输出格式】
第九章 动态规划
第二节 背包问题
第二节 背包问题
一、01背包问题 问题：
有N件物品和一个容量为V的背包。第i件物品的费用（即体积，下同）是w[i]， 价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量， 且价值总和最大。 基本思路：

刷表法——手推
【样例输入】package.in
10 4
21
for(int i=1;i<=n;++i)
Hale Waihona Puke 33for(int v=m;v>=w[i];--v)
45
f[v]=max(f[v],f[v-w[i]]+c[i])
79
【样例输出】package.out
12
i
W[i]
C[i]
i=0
0
0
i=1
2
1
i=2
理一件物品，作为一个阶段，共有n个 阶段 2、定义状态：
定义f[i][v]是前i件物品恰好放 入一个容量为v的背包，所得到的最大 价值 3、状态转移方程： 若第i件物品没有放入背包，则f[i][v]=f[i-
1][v] 若第i件物品放入背包，则f[i][v]=f[i-1][v-
w[i]]+c[i] 根据状态定义，f[i][v]=max(f[i-1][v],f[i-
【输出格式】 仅一行，一个数，表示最大总价值。
【样例输入】package.in 10 4 21 33 45 79
【样例输出】package.out 12
01背包
【问题描述】 一个旅行者有一个最多能用m公斤的
背包，现在有n件物品，它们的重量分别是 W1，W2，...,Wn,它们的价值分别为 C1,C2,...,Cn.若每种物品只有一件求旅行者 能获得最大总价值。 【输入格式】
1][v-w[i]]+c[i]) 4、临界值： 当i==0时，表示一件物品也没有， f[0][v]=0，数组f在main函数前定义即可
刷表法——手推
【样例输入】package.in 10 4