导引问题-食堂就餐
现有餐券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]}