背包问题学习笔记(2)-问法的变化

所有问法均以01背包问题为例,问题如下: 有\(N\)种物品和一个容量为\(V\)的背包,每种物品都有无限件可用。放入第i种物品的费用是\(C_i\),价值是\(W_i\),求背包所装物体的价值最大。 基本代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include
using namespace std;
const int N=4,V=10;
int F[N+1][V+1];
int C[N+1]={0,3,4,4,5};
int W[N+1]={0,4,6,6,7};
void BasicZeroOnePack() //O(NV)
{
memset(F,0,sizeof(F));
for(int i=1;i<=N;i++)
{
for(int v=0;v<=V;v++)
{
F[i][v]=F[i-1][v]; //默认不加入物品
if(v>=C[i]) //可以加入的时候考虑一下
F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]);
}
}
}

改动都是基于这个代码。

恰好装满的要求

如果要求恰好装满的话,初始化时除了\(F[0]=0\)以外,其余的F[1,…V]均设为负无穷。因为如果要求恰好装满,初始化的时候只有容量为0的背包装容量为0的物体才是合法状态,其余的状态全都不合法,用负无穷表示。

Read More

背包问题学习笔记(1)-基本的背包问题介绍

背包问题是动态规划中非常经典的问题。这里仅仅是一份学习笔记和简单的代码实现,更详细的介绍请见参考1和2。

01背包问题

题目

\(N\)种物品和一个容量为\(V\)的背包,每种物品都有无限件可用。放入第i种物品的费用是\(C_i\),价值是\(W_i\)。求解:将哪些物品装入背包,可使这些物品的耗费的费用总和不超过背包容量,且价值总和最大。

基本思路

\(F[i,v]\)代表前\(i\)件物品放入容量为\(v\)的背包可以获得的最大价值。 01背包的状态转移方程为: \[F[i,v]=\max\{F[i-1][v],F[i-1][v-C_i]+W_i\}\] 将“前\(i\)件物品放入容量为\(v\)的背包”中这个子问题,只考虑地\(i\)件物品的策略(放或不放)。如果放入\(i\)物品,问题转为“前i-1件物品放入容量为\(v-C_i\) 的背包中“这个子问题的最大价值\(F[i-1,v-C_i]\)加上\(W_i\)。如果不放,问题转化为”前i-1件物品放入容量为\(v-C_i\) 的背包中“,价值为\(F[i-1,v]\)

代码是

Read More