背包算法(Knapsack Algorithm)

导引问题-食堂就餐

现有餐券1张,面值10元。

菜肴N种:炸鸡腿8元;大排5元;荷包蛋:4元;炒青菜:3元;番茄炒蛋:4元……

餐券的特点:一次性使用,不找零;

问:若每种菜只能选一个,为了充分发挥餐券的作用,最多可以消费多少元?

什么是背包问题:

背包问题的基本模型:

给你一个容量为V的背包和若干种物品,在一定的限制条件下(每种物品都占用一定容量),问最多能放进多少价值的物品?

此类问题为指数级的问题

背包问题:

1.最典型、最基本的DP问题;

2.理解并熟练掌握背包问题意义重大;

3.DP问题中“状态”概念的理解;

4.背包的每个容量就是“状态”(思考一下杯子倒水问题中的状态转移);

背包问题的分类

1)01背包

2)完全背包

3)多重背包

4)二维费用背包

5)混合三种背包

6)分组背包

7)有依赖的背包

一、01背包

01背包(最基础的背包问题):

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

问题特点:每种物品仅有一件,可以选择放或不放;

思考:在每个物品都有可能被选中的前提下,如何构造“子问题”?

无序变有序的方法:依次考虑前1、前2、前3...前i个物品;

状态定义:f[i][v]表示前i件物品放入一个容量为v的背包可以获得的最大价值。

01问题的伪代码如下:

for i = 1 to n // 所有物品

        for j = V to v[i] // 思考:为何没必要循环到0?

                dp[j] = max(dp[j],dp[j-v[i]] + w[i]);

空间成功优化到一维V。

二、完全背包

完全背包特点:一种物品可以取无数个

可否转化成01背包问题?

朴素的转化方式是?

回忆01背包为何要对容量按照逆序循环?

和01背包类似,不过就是正着写!

深度思考:这类能不能达到的问题应该怎么实现?

三、多重背包

多重背包特点:

一种物品有C个(既不是固定的1个,也不是无数个)

优化的方法:

运用二进制,进行物品拆分,转化成01背包。

比如:13个相同的物品可分成4组(1,2,4,6)

用这4组可以组成任意一个1~13之间的数!

原理:一个数总可以用2^k表示

而且总和等于13,所以不会组成超过13的数

所以可将一种有C个的物品拆分成:

1,2,4,...,2^(k-1),C-(2^k-1)

然后进行01背包。

优化部分的参考代码:

int t=1;
while(x>=t)
{
	v[cnt]=a*t;
	c[cnt++]=b*t;
	x-=t;
	t<<=1; 
}

if(x)
{
	v[cnt]=a*x;
	c[cnt++]=b*x;
}

四、二维费用背包

二维费用背包问题:

对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(比如,背包容量、最大承重),求怎样选择物品可以得到最大的价值。

设第i件物品所需的两种代价分别为a[i]和b[i],两种代价可付出的最大值(比如体积和重量)分别为V和U,物品的价值为w[i]。

对应算法:费用加了一维,只需状态也加一维即可!

设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值,状态转移方程则为:

f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}

上一篇:spring boot rest例子


下一篇:2016 USP Try-outs The Knapsack problem