基地校活动心得(2019.07.25)

今天讲了高深基础算法,分别是递推,贪心,分治,它们都简狂。


递推

其实就是找规律(状态转移方程),但会把你 算||找 到吐,比如说铺瓷砖
首先,我们先把n=1-4的输出写出来

n=1 n=2 n=3 n=4
1 2 3 5

可以得出f[i]=f[i-1]+f[i-2],同时,定义f[1]=1,f[2]=2,然后就好了!

真简单

贪心

由局部最优解扩展到全局最优解,注意,你的贪心不一定正确,如果你想用贪心解决问题,要试着用反例否定它.

举个栗子:

非自然死亡

题目内容和标题好像没有什么关系

首先,两格的距离不包括斜对角线,题目没有说清楚.这题看似是比赛压轴,实际上简单,我们从左上角开始遍历棋盘,如果没有标记,就放一个棋子,然后把它周围两格距离的格子标记.于是,你就可以得到最优解了!

真简单+1

分治

分开来算!减少数据规模!让你的题目不再超时!

再举个栗子

求a^b%9 (b<=2^64)

如题,有的人可能会疑惑,直接pow(a,b)%9不就好了吗?看!(b&lt;=2^64) ,pow(a,b)%9时间复杂度是O(b),而2^64=18446744073709551616,不超时才怪;

所以,我们要用分治

先认为a=2,b=10;那么2^10=2^5*2^5,我们可以不重复计算2^5,同理可得

2^10=2^5*2^5;
2^5=2^2*2^2*2;
2^2=2*2;

数的计算(2019/07/24)

第一篇博客,写的不好请见谅

这是一道NOIP的水题,先看题目:

数的计算

题目描述

我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1.          不作任何处理;
2.          在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3.          加上数后,继续按此规则进行处理,直到不能再加自然数为止.

输入

一个数n

输出

 一个数表示答案

样例输入

6

样例输出

6

 

看完题目,很显然,这道题可以用暴力,但众所周知,暴力出超时,所以我们要用打表递推的方式解决这道题。

我们以4为例,4后面可以跟1,2,所以只要算出1,2的所有可能性的和,就是4的所有可能性。我们来手动模拟一下:
f[1]=1;
f[2]=2=f[1]+1;
f[3]=2=f[1]+1;
f[4]=4=f[1]+f[2]+1;

代码如下


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>//万能头
using namespace std;
int main(){
    //文件读写
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
   
    int n,f[10001],i,j;//定义变量
    //输入
    cin>>n;
    //核心代码
    for(i=1;i<=n;i++){//1至n
        for(j=1;j<=i/2;j++){//只循环一半
            f[i]+=f[j];//加上之前的可能性
        }
        f[i]++;//加上自身的可能性
    }
    //---------分界线----------
    cout<<f[n];//直接输出
    return 0;
}

背包问题

第三节  背包问题

 

一、01背包问题

问题:

N件物品和一个容量为V的背包。第i件物品的费用(即体积,下同)是w[i],价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

 

基本思路:

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:f[i,v]=max{f[i-1,v],f[i-1,v-w[i]]+c[i]}。

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”;如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”,此时能获得的最大价值就是f [i-1,v-w[i]]再加上通过放入第i件物品获得的价值c[i]。

注意f[i,v]有意义当且仅当存在一个前i件物品的子集,其费用总和为v。所以按照这个方程递推完毕后,最终的答案并不一定是f[N,V],而是f[N,0..V]的最大值。如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项f[i,v-1],这样就可以保证f[N,V]就是最后的答案。至于为什么这样就可以,由你自己来体会了。

 

优化空间复杂度

以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。

 

先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i,0..V]的所有值。那么,如果只用一个数组f [0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i,v]呢?f[i,v]是由f[i-1,v]和f[i-1,v-w[i]]两个子问题递推而来,能否保证在推f[i,v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1,v]和f[i-1,v-w[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-w[i]]保存的是状态f[i-1,v-w[i]]的值。

伪代码如下:

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-w[i]]+c[i]};

 

其中f[v]=max{f[v],f[v-w[i]]}相当于转移方程f[i,v]=max{f[i-1,v],f[i-1,v-w[i]]},因为现在的f[v-w[i]]就相当于原来的f[i-1,v-w[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i,v]由f[i,v-w[i]]推知,与本题意不符,但它却是另一个重要的完全背包问题最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的

101背包问题

【问题描述】

一个旅行者有一个最多能用M公斤的背包,现在有n件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

【输入格式】

第一行:两个整数,M(背包容量,M<=200)和N(物品数量,N<=30);

第2..N+1行:每行二个整数Wi,Ci,表示每个物品的重量和价值。

【输出格式】

仅一行,一个数,表示最大总价值。

【样例输入】package.in

10 4

2  1

3  3

4  5

7  9

【样例输出】package.out

12

【解法一】

【算法分析】

设f(i,x)表示前i件物品,总重量不超过v的最优价值,则 f(i,v)=max(f(i-1,v-w[i])+c[i],f(i-1,v)) ;f(n,m)即为最优解。

【参考程序】

program package;

const  maxm=200;maxn=30;

var  m,n,v,i:integer;

c,w: array[1..maxn] of integer;

f:array[0..maxn,0..maxm] of integer;

function max(x,y:integer):integer;       //求x和y最大值

begin

if x>y then max:=x else max:=y;

end;

BEGIN

assign(input,'package.in');  reset(input);

assign(output,'package.out');rewrite(output);

readln(m,n);                       //背包容量m和物品数量n

for i:= 1 to n do

readln(w[i],c[i]);                //每个物品的重量和价值

for i:=1 to n do

for v:=1 to m do

begin                     // f(i,x)表示前i件物品,总重量不超过x的最优价值

if v>=w[i]  then f[i,v]:=max(f[i-1,v-w[i]]+c[i],f[i-1,v])

else f[i,v]:=f[i-1,v];

end;

writeln(f[n,m]);        // f(n,m)为最优解

close(input);   close(output);

END.

使用二维数组存储各子问题时方便,但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组。

 

【解法二】

【算法分析】

本问题的数学模型如下:设 f(v)表示重量不超过v公斤的最大价值, f(v)=max{f(v)f(v-w[i])+c[i]} 

v>=w[i]1<=i<=n

【参考程序】

program star_package;

var

i,v,k,n,m:longint;

f:array[0..100000]of longint;

w,c:array[0..2000]of longint;

begin

assign(input,'package.in'); reset(input);

assign(output,'package.out'); rewrite(output);

fillchar(f,sizeof(f),0);

readln(m,n);                   //背包容量m和物品数量n

for i:=1 to n do

readln(w[i],c[i]);           //每个物品的重量和价值

for i:=1 to n do

for v:=m downto w[i] do      //设 f(v)表示重量不超过v公斤的最大价值

if f[v-w[i]]+c[i]>f[v] then f[v]:=f[v-w[i]]+c[i];

 

for v:=1 to m do         //设 f(v)表示重量不超过v公斤的最大价值

for i:=1 to n do

begin

if v>=w[i] then if f[v-w[i]]+c[i]>f[v] then f[v]:= f[v-w[i]]+c[i] ;

end;

 

 

 

writeln(f[m]);                 // f(m)为最优解

close(input);close(output);

end.

 

总结:

01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。

 

二、完全背包问题

问题:

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

 

基本思路:

这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,令f[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:f[i,v]=max{f[i-1,v-k*w[i]]+k*c[i]|0<=k*w[i]<= v}。这跟01背包问题一样有O(N*V)个状态需要求解,但求解每个状态的时间则不是常数了,求解状态f[i,v]的时间是O(v/w[i]),总的复杂度是超过O(VN)的。

将01背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要,可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。

 

一个简单有效的优化

完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足w[i]<=w[j]且c[i]>=c[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高的j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。

 

转化为01背包问题求解

既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/w[i]件,于是可以把第i种物品转化为V/w[i]件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。

更高效的转化方法是:把第i种物品拆成费用为w[i]*2^k、价值为c[i]*2^k的若干件物品,其中k满足w[i]*2^k<V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/w[i]))件物品,是一个很大的改进。但我们有更优的O(VN)的算法。

这个算法使用一维数组,先看伪代码:

for i=1..N

for v=0..V

f[v]=max{f[v],f[v-w[i]]+c[i]};

你会发现,这个伪代码与01背包问题的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢?首先想想为什么01背包问题中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i,v]是由状态f[i-1,v-w[i]]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果f[i-1,v-w[i]]。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果f[i,v-w[i]],所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。

这个算法也可以以另外的思路得出。例如,基本思路中的状态转移方程可以等价地变形成这种形式:f[i,v]=max{f[i-1,v],f[i,v-w[i]]+c[i]},将这个方程用一维数组实现,便得到了上面的伪代码。

 

 

 

2、完全背包问题

【问题描述】

设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M,而价值的和为最大。

【输入格式】

第一行:两个整数,M(背包容量,M<=200)和N(物品数量,N<=30);

第2..N+1行:每行二个整数Wi,Ci,表示每个物品的重量和价值。

【输出格式】

仅一行,一个数,表示最大总价值。

【样例输入】knapsack.in

10 4

2  1

3  3

4  5

7  9

【样例输出】knapsack.out

max=12

 

【解法一】

【算法分析】

本问题的数学模型如下:

设 f(v)表示重量不超过v公斤的最大价值, 则 f(v)=max{f(v),f(v-w[i])+c[i]}

当v>=w[i] ,1<=i<=n 。

【参考程序】

program knapsack04;

const  maxm=200;maxn=30;

type   ar=array[0..maxn] of integer;

var

m,n,v,i,t:integer;

c,w:ar;

f:array[0..maxm] of integer;

BEGIN

assign(input,'knapsack.in');  reset(input);

assign(output,'knapsack.out'); rewrite(output);

readln(m,n);            //背包容量m和物品数量n

for i:= 1 to n do

readln(w[i],c[i]);      //每个物品的重量和价值

f[0]:=0;

for v:=1 to m do         //设 f(v)表示重量不超过v公斤的最大价值

for i:=1 to n do

begin

if v>=w[i] then if f[v-w[i]]+c[i]>f[v] then f[v]:= f[v-w[i]]+c[i] ;

end;

for i:=1 to n do          //f(i,v)表示前i件物品,总重量不超过v的最优价值

for v:=1 to m do

if v<w[i] then f[i,v]:=f[i-1,v]

else if f[i-1,v]>f[i,v-w[i]]+c[i]  then  f[i,v]:=f[i-1,v]

else  f[i,v]:=f[i,v-w[i]]+c[i];

for i:=1 to n do

for v:=1 to m do

begin                     // f(i,x)表示前i件物品,总重量不超过x的最优价值

if v>=w[i]  then f[i,v]:=max(f[i-1,v-w[i]]+c[i],f[i-1,v])

else f[i,v]:=f[i-1,v];

 

 

 

writeln(‘max=’,f[m]);    // f(m)为最优解

close(input);close(output);

END.

 

【解法二】

【算法分析】

设 f(i,v)表示前i件物品,总重量不超过v的最优价值,则 f(i,v)=max(f(i,v-w[i])+c[i],f(i-1,v)) ;f(n,m)即为最优解。

【参考程序】

Program knapsack;

Const

maxm=200;maxn=30;

var

i,v,n,m:integer;

w,c:array[1..maxn] of integer;

f:array[0..maxn,0..maxm] of integer;

BEGIN

assign(input,'knapsack.in');  reset(input);

assign(output,'knapsack.out');rewrite(output);

fillchar(w,sizeof(w),0);

fillchar(c,sizeof(c),0);

readln(m,n);            //背包容量m和物品数量n

for i:=1 to n do          //每个物品的重量和价值

read(w[i],c[i]);

for i:=1 to n do          //f(i,v)表示前i件物品,总重量不超过v的最优价值

for v:=1 to m do

if v<w[i] then f[i,v]:=f[i-1,v]

else if f[i-1,v]>f[i,v-w[i]]+c[i]  then  f[i,v]:=f[i-1,v]

else  f[i,v]:=f[i,v-w[i]]+c[i];

writeln('max=', f[n,m]);   // f(n,m)为最优解

close(input); close(output);

END.

 

总结

完全背包问题也是一个相当基础的背包问题,它有两个状态转移方程,分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会,不仅记住,也要弄明白它们是怎么得出来的,最好能够自己想一种得到这些方程的方法。事实上,对每一道动态规划题目都思考其方程的意义以及如何得来,是加深对动态规划的理解、提高动态规划功力的好方法。

 

 

 

 

 

三、多重背包问题

问题

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

 

基本算法:

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]件。令f[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值,则:f[i,v]=max{f[i-1,v-k*w[i]]+ k*c[i]|0<=k<=n[i]}。复杂度是O(V*∑n[i])。

 

转化为01背包问题

另一种好想好写的基本方法是转化为01背包求解:把第i种物品换成n[i]件01背包中的物品,则得到了物品数为∑n[i]的01背包问题,直接求解,复杂度仍然是O(V*∑n[i])。

但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想,我们考虑把第i种物品换成若干件物品,使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外,取超过n[i]件的策略必不能出现。

方法是:将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,...,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。

分成的这几件物品的系数和为n[i],表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数,均可以用若干个系数的和表示,这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出,并不难,希望你自己思考尝试一下。

这样就将第i种物品分成了O(logn[i])种物品,将原问题转化为了复杂度为O(V*∑logn[i])的01背包问题,是很大的改进。

 

O(VN)的算法

多重背包问题同样有O(VN)的算法。这个算法基于基本算法的状态转移方程,但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解。由于用单调队列优化的DP已超出了NOIP的范围,故本文不再展开讲解。我最初了解到这个方法是在楼天成的“男人八题”幻灯片上。

 

3逃亡的准备

【问题描述】

在《Harry Potter and the Deathly Hallows》中,Harry Potter他们一起逃亡,现在有许多的东西要放到赫敏的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品,现在给出该种物品的数量、体积、价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,赫敏会非常地感谢你。

【输入文件】hallows.in

第一行有2个整数,物品种数n和背包装载体积v。

2行到i+1行每行3个整数,为第i种物品的数量m、体积w、价值s。

【输出文件】hallows.out

输出文件hallows.out仅包含一个整数,即为能拿到的最大的物品价值总和。

【输入样例】

2 10

3 4 3

2 2 5

【输出样例】

13

【注释】

选第一种一个,第二种两个。结果为3*1+5*2=13

【数据规模】

对于30%的数据

1<=v<=500,1<=n<=2000,1<=m<=10,1<=w<=20,1<=s<=100

对于100%的数据

1<=v<=500,1<=n<=2000,1<=m<=5000,1<=w<=20,1<=s<=100

【算法分析】

本题一看就看出是背包问题,如果在物品个数m较小的时候可以在传统背包加一层循环,循环m次,就可以轻松求解。可是m<=5000,这种方法肯定超时。因为m较大,那么m*w就可能大于v。所以对于m*w>=v的物品可以转化为完全背包,这样题目的思路就清晰了。预处理时将物品分为可以用完全背包求解的和0/1背包求解的,两个背包求解可以在一个一维数组中实现。

 

小结

这里我们看到了将一个算法的复杂度由O(V*∑n[i])改进到O(V*∑logn[i])的过程,还知道了存在应用超出NOIP范围的知识的O(VN)算法。希望你特别注意“拆分物品”的思想和方法,自己证明一下它的正确性,并用尽量简洁的程序来实现。

 

四、混合三种背包问题

问题

如果将01背包、完全背包、多重背包混合起来。也就是说,有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。应该怎么求解呢?

 

01背包与完全背包的混合

考虑到在01背包完全背包中最后给出的伪代码只有一处不同,故如果只有两类物品:一类物品只能取一次,另一类物品可以取无限次,那么只需在对每个物品应用转移方程时,根据物品的类别选用顺序或逆序的循环即可,复杂度是O(VN)。伪代码如下:

for i=1..N

if 第i件物品是01背包

for v=V..0

f[v]=max{f[v],f[v-w[i]]+c[i]};

else if 第i件物品是完全背包

for v=0..V

f[v]=max{f[v],f[v-w[i]]+c[i]};

 

再加上多重背包

如果再加上有的物品最多可以取有限次,那么原则上也可以给出O(VN)的解法:遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话,用多重背包中将每个这类物品分成O(log n[i])个01背包的物品的方法也已经很优了。

 

4暗黑游戏

【问题描述】

暗黑游戏中,装备直接决定玩家人物的能力。可以使用Pg和Rune购买需要的物品。暗黑市场中的装备,每件有不同的价格(Pg和Rune)、能力值、最大可购买件数。Kid作为暗黑战网的一个玩家,当然希望使用尽可能少的Pg和Rune购买更优的装备,以获得最高的能力值。请你帮忙计算出现有支付能力下的最大可以获得的能力值。

【输入格式】

第一行,三个整数N,P,R,分别代表市场中物品种类,Pg的支付能力和Rune的支付能力。

第2..N+1行,每行四个整数,前两个整数分别为购买此物品需要花费的Pg,Rune,第三个整数若为0,则说明此物品可以购买无数件,若为其他数字,则为此物品可购买的最多件数(S),第四个整数为该装备的能力值。

【输出格式】

仅一行,一个整数,最大可获得的能力值。

【输入样例】

3 10 10

5 3 0 110

4 3 4 120

2 3 1 130

【输出样例】

370

【数据规模】

对于30%的数据, 0<N<=50, 0<P<=30, 0<R<=30, 0<=S<=8;

对于70%的数据, 0<N<=80, 0<P<=65, 0<R<=65, 0<=S<=16;

对于100%的数据, 0<N<=150, 0<P<=100, 0<R<=100, 0<=S<=32;

样例解释

    选第二种装备2件和第三种装备1件。

小结

有人说,困难的题目都是由简单的题目叠加而来的。这句话是否公理暂且存之不论,但它在本讲中已经得到了充分的体现。本来01背包、完全背包、多重背包都不是什么难题,但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要基础扎实,领会三种基本背包问题的思想,就可以做到把困难的题目拆分成简单的题目来解决。

 

 

 

 

 

 

 

 

 

 

五、二维费用的背包问题

问题

二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]b[i]。两种代价可付出的最大值(两种背包容量)分别为VU。物品的价值为c[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]]+c[i]}。如前述方法,可以只使用二维的数组:当每件物品只可以取一次时变量v和u采用顺序的循环,当物品有如完全背包问题时采用逆序的循环。当物品有如多重背包问题时拆分物品。

 

物品总个数的限制

有时,“二维费用”的条件是以这样一种隐含的方式给出的:最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用,每个物品的件数费用均为1,可以付出的最大件数费用为M。换句话说,设f[v,m]表示付出费用v、最多选m件时可得到的最大价值,则根据物品的类型(01、完全、多重)用不同的方法循环更新,最后在f[0..V,0..M]范围内寻找答案。

另外,如果要求“恰取M件物品”,则在f[0..V,M]范围内寻找答案。

 

例5潜水员

问题描述

潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸:一个为氧气,一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少?

例如:潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量:

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号气缸)。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

【输入格式】

第一行有2整数m,n(1<=m<=21,1<=n<=79)。它们表示氧,氮各自需要的量。

第二行为整数k(1<=n<=1000)表示气缸的个数。

此后的k行,每行包括ai,bi,ci(1<=ai<=21,1<=bi<=79,1<=ci<=800)3整数。这些各自是:第i个气缸里的氧和氮的容量及汽缸重量。

【输出格式】

仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。

【输入样例】

5 60

5

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

【输出样例】

249

【参考程序】

program czx;

var  a,b,c:array [1..1000]  of longint;

f:array [0..100,0..100] of longint;

m,n,k,i,j,l,t1,t2:longint;

begin

assign(input,'gas.in'); reset(input);

assign(output,'gas.out');rewrite(output);

fillchar(f,sizeof(f),$7f);

readln(m,n);

readln(k);

for i:=1 to k do readln(a[i],b[i],c[i]);

f[0,0]:=0;

for i:=1 to k do

for j:=m downto 0 do

for l:=n downto 0 do

begin

if j+a[i]>m then t1:=m else t1:=j+a[i];

if l+b[i]>n then t2:=n else t2:=l+b[i];

if f[j,l]+c[i]<f[t1,t2] then f[t1,t2]:=f[j,l]+c[i];

end;

writeln(f[m,n]);

close(input);close(output);

end.

 

小结

事实上,当发现由熟悉的动态规划题目变形得来的题目时,在原来的状态中加一纬以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。

 

 

 

 

 

六、分组的背包问题

问题

N件物品和一个容量为V的背包。第i件物品的费用是w[i],价值是c[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

 

算法

这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设f[k,v]表示前k组物品花费费用v能取得的最大权值,则有f[k,v]=max{f[k-1,v],f[k-1,v-w[i]]+c[i]|物品i属于第k组}。

 

使用一维数组的伪代码如下:

for 所有的组k

for v=V..0

for 所有的i属于组k

f[v]=max{f[v],f[v-w[i]]+c[i]}

注意这里的三层循环的顺序,“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

另外,显然可以对每组中的物品应用完全背包中“一个简单有效的优化”。

 

例6、分组背包

【问题描述】

一个旅行者有一个最多能用V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

【输入格式】

第一行:三个整数,V(背包容量,M<=200),N(物品数量,N<=30)和T(所属组号,T<=10);

第2..N+1行:每行三个整数Wi,Ci,P,表示每个物品的重量,价值,所属组号。

【输出格式】

仅一行,一个数,表示最大总价值。

【样例输入】group.in

10 6 3

2  1  1

3  3  1

4  8  2

6  9  2

2  8  3

3  9  3

【样例输出】group.out

20

 

 

例6、机器分配

【问题描述】

总公司拥有高效设备M台,准备分给下属的N个分公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M≤15,N≤10。分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数M。

输入数据为:第一行有两个数,第一个数是分公司数N,第二个数是设备台数M。

接下来是一个N*M的矩阵,表明了第 I个公司分配 J台机器的盈利。

【输入样例】assigned.in

3 3                                            //3个分公司分3台机器

30 40 50

20 30 50

20 25 30

【输出样例】assigned.out

70                                             //最大盈利值为70

1 1                                             //第一分公司分1台

2 1                                             //第二分公司分1台

3 1                                             //第三分公司分1台

【算法分析】

按照公司的顺序来分配机器,即按照公司的顺序划分阶段,第一个阶段把M台设备分给第一个公司,记录下来获得的各个盈利值,然后把M台设备分给前两个公司,和第一个阶段比较记录下来更优的各个盈利值,一直到第N个阶段把M台机器全部分给了N个公司,就可以得到最优解,下面来讨论两个阶段之间的关系,设数组F[I,J]表示前I个公司分配J台机器的最大盈利,数组F[I-1,K]表示前I-1个公司分配K台机器的最大盈利(1≤I≤N,1≤J≤M,0≤K≤J),,用Valvu[I,J]表示第I个公司分配 J台机器的盈利, 则F[I,J]可以由下面的式子中取最大值获得:

F[I-1,0]+Value[I,J]  //前I-1公司分配0台机器+第I个公司分配J台的机器的最大盈利

F[I-1,1]+Value[I,J-1] //前I-1公司分配1台机器+第I个公司分配J-1台的机器的最大盈利

F[I-1,2]+Value[I,J-2] //前I-1公司分配2台机器+第I个公司分配J-2台的机器的最大盈利

F[I-1,J-1]+Value[I,1] //前I-1公司J-1分配台机器+第I个公司分配1台的机器的最大盈利

F[I-1,J]+Value[I,0]  //前I-1公司分配J台机器+第I个公司分配0台的机器的最大盈利

在这里用机器数用做每个阶段的状态,由于Value[I,J]的值为定值,要使前面每个式子的值最大,就必须使第i-1阶段的各个状态的值最大,阶段i的状态只能由阶段i-1中的状态通过状态转移方程求得,与其他状态没有关系。由此可见,该问题具备了最优子结构和无后效性原则,适宜使用动态程序设计方法求解。

状态转移方程为:F[I,J]=MAX{F[I-1,K]+Value[I,J-K]} (1≤I≤N,1≤J≤M,0≤K≤J)

初始值:F[0,0]=0,F[n,m]的值即为所求最大盈利值。

【参考程序】

program  dissigned;

var  m,n:integer;

I,j,k,max:longint;

F,value:array[0..10,0..15] of  integer;

procedure  show(i,j:longint);              //输出各分公司分配情况

var  k:longint;

begin

if  i=0  then  exit;

for  k:=0  to  j do

if  max=f[i-1,k]+value[i,j-k]  then

begin

max:=f[i-1,k];

show(i-1,k);

writeln(i,‘ ‘,j-k);

exit;

end;

end;

BEGIN

readln(n,m);

for I:= 1  to  n  do

for j:= 1  to  m  do

read(value[i,j]);

for i:= 1  to  n  do

for j:=1  to  m  do

begin

max:=0;

for k:= 0  to  j  do

if f[i-1,k]+value[i,j-k]>max  then  max:=f[i-1,k] + value[i,j-k];

f[i,j]:=max;

end;

writeln(f[n,m]);                          //输出最大盈利值

show(n,m);                              //输出分配情况

END.

 

小结

分组的背包问题将彼此互斥的若干物品称为一个组,这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题。

 

七、有依赖的背包问题P07

简化的问题

这种背包问题的物品间存在某种“依赖”的关系。也就是说,i依赖于j,表示若选物品i,则必须选物品j。为了简化起见,我们先设没有某个物品既依赖于别的物品,又被别的物品所依赖;另外,没有某件物品同时依赖多件物品。

算法:

这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法,将不依赖于别的物品的物品称为“主件”,依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。

按照背包问题的一般思路,仅考虑一个主件和它的附件集合。可是,可用的策略非常多,包括:一个也不选,仅选择主件,选择主件后再选择一个附件,选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。(事实上,设有n个附件,则策略有2^n+1个,为指数级。)

考虑到所有这些策略都是互斥的(也就是说,你只能选择一种策略),所以一个主件和它的附件集合实际上对应于分组的背包中的一个物品组,每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品,其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法,因为物品组中的物品还是像原问题的策略一样多。

再考虑分组的背包中的一句话: 可以对每组中的物品应用完全背包中“一个简单有效的优化”。这提示我们,对于一个物品组中的物品,所有费用相同的物品只留一个价值最大的,不影响结果。所以,我们可以对主件i的“附件集合”先进行一次01背包,得到费用依次为0..V-w[i]所有这些值时相应的最大价值f'[0..V-w[i]]。那么这个主件及它的附件集合相当于V-w[i]+1个物品的物品组,其中费用为w[i]+k的物品的价值为f'[k]+c[i]。也就是说原来指数级的策略中有很多策略都是冗余的,通过一次01背包后,将主件i转化为 V-w[i]+1个物品的物品组,就可以直接应用分组的背包的算法解决问题了。

更一般的问题是依赖关系以图论中“森林”的形式给出(森林即多叉树的集合),也就是说,主件的附件仍然可以具有自己的附件集合,限制只是每个物品最多只依赖于一个物品(只有一个主件)且不出现循环依赖。

解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是,由于附件可能还有附件,就不能将每个附件都看作一个一般的01 背包中的物品了。若这个附件也有附件集合,则它必定要被先转化为物品组,然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。

事实上,这是一种树形DP,其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后,你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品,求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。

 

小结

NOIP2006的那道背包问题,通过引入“物品组”和“依赖”的概念可以加深对这题的理解,还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系:物品不能既作主件又作附件,每个主件最多有两个附件,可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组,这便揭示了问题的某种本质。

 

P08: 泛化物品

定义

考虑这样一种物品,它并没有固定的费用和价值,而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。

更严格的定义之。在背包容量为V的背包问题中,泛化物品是一个定义域为0..V中的整数的函数h,当分配给它的费用为v时,能得到的价值就是h(v)

这个定义有一点点抽象,另一种理解是一个泛化物品就是一个数组h[0..V],给它费用v,可得到价值h[V]

一个费用为c价值为w的物品,如果它是01背包中的物品,那么把它看成泛化物品,它就是除了h(c)=w其它函数值都为0的一个函数。如果它是完全背包中的物品,那么它可以看成这样一个函数,仅当vc整除时有h(v)=v/c*w,其它函数值均为0。如果它是多重背包中重复次数最多为n的物品,那么它对应的泛化物品的函数有h(v)=v/c*w仅当vc整除且v/c<=n,其它情况函数值均为0

一个物品组可以看作一个泛化物品h。对于一个0..V中的v,若物品组中不存在费用为v的的物品,则h(v)=0,否则h(v)为所有费用为v的物品的最大价值。P07中每个主件及其附件集合等价于一个物品组,自然也可看作一个泛化物品。

 

泛化物品的和

如果面对两个泛化物品h和l,要用给定的费用从这两个泛化物品中得到最大的价值,怎么求呢?事实上,对于一个给定的费用v,只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的,对于0..V的每一个整数v,可以求得费用v分配到h和l中的最大价值f(v)。也即f(v)=max{h(k) +l(v-k)|0<=k<=v}。可以看到,f也是一个由泛化物品h和l决定的定义域为0..V的函数,也就是说,f是一个由泛化物品h和 l决定的泛化物品。

由此可以定义泛化物品的和:h、l都是泛化物品,若泛化物品f满足f(v)=max{h(k)+l(v-k)|0<=k<=v},则称f是h与l的和,即f=h+l。这个运算的时间复杂度是O(V^2)。

泛化物品的定义表明:在一个背包问题中,若将两个泛化物品代以它们的和,不影响问题的答案。事实上,对于其中的物品都是泛化物品的背包问题,求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s,则答案就是s[0..V]中的最大值。

 

背包问题的泛化物品

一个背包问题中,可能会给出很多条件,包括每种物品的费用、价值等属性,物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说,给定了所有条件以后,就可以对每个非负整数v求得:若背包容量为v,将物品装入背包可得到的最大价值是多少,这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品——或者说问题所对应的一个定义域为非负整数的函数——包含了关于问题本身的高度浓缩的信息。一般而言,求得这个泛化物品的一个子域(例如0..V)的值之后,就可以根据这个函数的取值得到背包问题的最终答案。

综上所述,一般而言,求解背包问题,即求解这个问题所对应的一个函数,即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。

 

小结

本讲可以说都是我自己的原创思想。具体来说,是我在学习函数式编程的 Scheme 语言时,用函数编程的眼光审视各类背包问题得出的理论。这一讲真的很抽象,也许在“模型的抽象程度”这一方面已经超出了NOIP的要求,所以暂且看不懂也没关系。相信随着你的OI之路逐渐延伸,有一天你会理解的。

“思考”是一个OIer最重要的品质。简单的问题,深入思考以后,也能发现更多。

 

八、背包问题问法的变化

以上涉及的各种背包问题都是要求在背包容量(费用)的限制下求可以取到的最大价值,但背包问题还有很多种灵活的问法,在这里值得提一下。但是我认为,只要深入理解了求背包问题最大价值的方法,即使问法变化了,也是不难想出算法的。

例如,求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值(f数组)之后得到。

还有,如果要求的是“总价值最小”“总件数最小”,只需简单的将上面的状态转移方程中的max改成min即可。

下面说一些变化更大的问法。

输出方案

一般而言,背包问题是要求一个最优值,如果要求输出这个最优值的方案,可以参照一般动态规划问题输出方案的方法:记录下每个状态的最优值是由状态转移方程的哪一项推出来的,换句话说,记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态,从上一个状态接着向前推即可。

还是以01背包为例,方程为f[i,v]=max{f[i-1,v],f[i-1,v-w[i]]+c[i]}。再用一个数组g[i,v],设g[i,v]=0表示推出f[i,v]的值时是采用了方程的前一项(也即f[i,v]=f[i-1,v]),g[i,v]表示采用了方程的后一项。注意这两项分别表示了两种策略:未选第i个物品及选了第i个物品。那么输出方案的伪代码可以这样写(设最终状态为f[N,V]):

i=N

v=V

while(i>0)

if(g[i,v]==0)

print "未选第i项物品"

else if(g[i,v]==1)

print "选了第i项物品"

v=v-w[i]

另外,采用方程的前一项或后一项也可以在输出方案的过程中根据f[i,v]的值实时地求出来,也即不须纪录g数组,将上述代码中的g[i,v]==0改成f[i,v]==f[i-1,v],g[i,v]==1改成f[i,v]==f[i-1,v-w[i]]+c[i]也可。

 

输出字典序最小的最优方案

这里“字典序最小”的意思是1..N号物品的选择方案排列出来以后字典序最小。以输出01背包最小字典序的方案为例。

一般而言,求一个字典序最小的最优方案,只需要在转移时注意策略。首先,子问题的定义要略改一些。我们注意到,如果存在一个选了物品1的最优方案,那么答案一定包含物品1,原问题转化为一个背包容量为v-w[1],物品为2..N的子问题。反之,如果答案不包含物品1,则转化成背包容量仍为V,物品为2..N的子问题。不管答案怎样,子问题的物品都是以i..N而非前所述的1..i的形式来定义的,所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下,以下按物品已被逆序排列来叙述。

在这种情况下,可以按照前面经典的状态转移方程来求值,只是输出方案的时候要注意:从N到1输入时,如果f[i,v]==f[i-v]及f[i,v]==f[i-1,f-w[i]]+c[i]同时成立,应该按照后者(即选择了物品i)来输出方案。

 

求方案总数

对于一个给定了背包容量、物品费用、物品间相互关系(分组、依赖等)的背包问题,除了再给定每个物品的价值后求可得到的最大价值外,还可以得到装满背包或将背包装至某一指定容量的方案总数。

对于这类改变问法的问题,一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是01背包中的物品,转移方程即为f[i,v]=sum{f[i-1,v],f[i-1,v-w[i]]+c[i]},初始条件f[0,0]=1。

事实上,这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。

 

最优方案的总数

这里的最优方案是指物品总价值最大的方案。还是以01背包为例。

结合求最大总价值和方案总数两个问题的思路,最优方案的总数可以这样求:f[i,v]意义同前述,g[i,v]表示这个子问题的最优方案的总数,则在求f[i,v]的同时求g[i,v]的伪代码如下:

for i=1..N

for v=0..V

f[i,v]=max{f[i-1,v],f[i-1,v-w[i]]+c[i]}

g[i,v]=0

if(f[i,v]==f[i-1,v])

inc(g[i,v],g[i-1,v]

if(f[i,v]==f[i-1,v-w[i]]+c[i])

inc(g[i,v],g[i-1,v-w[i]])

如果你是第一次看到这样的问题,请仔细体会上面的伪代码。

 

求次优解、第K优解

对于求次优解、第K优解类的问题,如果相应的最优解问题能写出状态转移方程、用动态规划解决,那么求次优解往往可以相同的复杂度解决,第K优解则比求最优解的复杂度上多一个系数K。

其基本思想是将每个状态都表示成有序队列,将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。

首先看01背包求最优解的状态转移方程:

如果要求第K优解,那么状态f[i,v]就应该是一个大小为K的数组f[i,v,1..K]。其中f[i,v,k]表示前i个物品、背包大小为v时,第k优解的值。“f[i,v]是一个大小为K的数组”这一句,熟悉C语言的同学可能比较好理解,或者也可以简单地理解为在原来的方程中加了一维。显然f[i,v,1..K]这K个数是由大到小排列的,所以我们把它认为是一个有序队列。

然后原方程就可以解释为:f[i,v]这个有序队列是由f[i-1,v]和f[i-1,v-w[i]]+c[i]这两个有序队列合并得到的。有序队列f[i-1,v]即f[i-1,v,1..K],f[i-1,v-w[i]]+c[i]则理解为在f[i-1,v-w[i],1..K]的每个数上加上c[i]后得到的有序队列。合并这两个有序队列并将结果(的前K项)储存到f[i,v,1..K]中的复杂度是O(K)。最后的答案是f[N,V,K]。总的复杂度是O(NVK)。

为什么这个方法正确呢?实际上,一个正确的状态转移方程的求解过程遍历了所有可用的策略,也就覆盖了问题的所有方案。只不过由于是求最优解,所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组,并在这个数组中有序的保存该状态可取到的前K个最优值。那么,对于任两个状态的max运算等价于两个由大到小的有序队列的合并。

另外还要注意题目对于“第K优解”的定义,将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者,则维护有序队列时要保证队列里的数没有重复的。

 

8货币系统

【问题描述】

给你一个n种面值的货币系统,求组成面值为m的货币有多少种方案。样例:设n=3,m=10,要求输入和输出的格式如下:

【样例输入】money.in

3  10       //3种面值组成面值为10的方案

1           //面值1

2           //面值2

5           //面值5

【样例输出】money.out

10          //有10种方案

【算法分析1

设f(j)表示面值不超过j的最大方案数, 如果f(j-a[i])<>0则f(j)=f(j)+f(j-a[i]),1<=i<=n,a[i]<=j<=m。

【参考程序1

program money;

var f:array[0..10000] of qword;

a:array[0..1000] of longint;

m,n,i,j,k:longint;

begin

assign(input,'money.in'); reset(input);

assign(output,'money.out');rewrite(output);

readln(n,m);

for i:=1 to n do readln(a[i]);

fillchar(f,sizeof(f),0);  f[0]:=1;

for i:=1 to n do

for j:=a[i] to m do

f[j]:=f[j]+f[j-a[i]];

writeln(f[m]);

close(input);close(output);

end.

 

【算法分析2

设f(j)表示面值不超过j的最大方案数, 如果f(j-k*a[i])<>0则f(j)=f(j)+f(j-k*a[i]),当1<=i<=n,m>=j>= a[i],1<=k<=j div a[i]。

【参考程序2

program money;

var f:array[0..100000]of qword;

a:array[0..1000]of longint;

m,n,i,j,k:longint;

begin

assign(input,'money.in');  reset(input);

assign(output,'money.out');rewrite(output);

readln(n,m);                 //n种面值的货币,组成面值为m

for i:=1 to n do readln(a[i]);   //输入每一种面值

fillchar(f,sizeof(f),0);  f[0]:=1;

for i:=1 to n do

for j:=m downto a[i] do      //f(j)表示面值不超过j的最大方案数

for k:=1 to (j div a[i]) do

if f[j-k*a[i]]<>0 then f[j]:=f[j]+f[j-k*a[i]];

writeln(f[m]);                // f(m)为最优解

close(input);close(output);

end.

 

题9、多人背包

【问题描述】

DD和好朋友们要去爬山啦!他们一共有 K 个人,每个人都会背一个包。这些包的容量是相同的,都是 V。可以装进背包里的一共有 N 种物品,每种物品都有给定的体积和价值。在 DD 看来,合理的背包安排方案是这样的:

  1. 每个人背包里装的物品的总体积恰等于包的容量。
  2. 每个包里的每种物品最多只有一件,但两个不同的包中可以存在相同的物品。
  3. 任意两个人,他们包里的物品清单不能完全相同。

在满足以上要求的前提下,所有包里的所有物品的总价值最大是多少呢?

【输入格式】

第一行有三个整数:K、V、N。

第二行开始的 N 行,每行有两个整数,分别代表这件物品的体积和价值。

【输出格式】

只需输出一个整数,即在满足以上要求的前提下所有物品的总价值的最大值。

【输入样例】

    2 10 5

    3 12

    7 20

    2 4

    5 6

    1 1

【输出样例】

    57

【样例说明】

一种可以得到最优解的方案是:第一个人背体积为 7、2、1 的三种物品,价值为 25。第二个人背体积为 3、7 的两种物品,价值为 32。总价值 57。

【数据规模】

总人数 K<=50,每个背包的容量 V<=5000,物品种类数 N<=200。

其它正整数都不超过 5000,输入数据保证存在满足要求的方案。

【算法分析】

对于求次优解、第K优解类的问题,如果相应的最优解问题能写出状态转移方程、用动态规划解决,那么求次优解往往可以相同的复杂度解决,第K优解则比求最优解的复杂度上多一个系数K。

其基本思想是将每个状态都表示成有序队列,将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。

首先看01背包求最优解的状态转移方程:

如果要求第K优解,那么状态f[i,v]就应该是一个大小为K的数组f[i,v,1..K]。其中f[i,v,k]表示前i个物品、背包大小为v时,第k优解的值。“f[i,v]是一个大小为K的数组”这一句,熟悉C语言的同学可能比较好理解,或者也可以简单地理解为在原来的方程中加了一维。显然f[i,v,1..K]这K个数是由大到小排列的,所以我们把它认为是一个有序队列。

然后原方程就可以解释为:f[i,v]这个有序队列是由f[i-1,v]和f[i-1,v-w[i]]+c[i]这两个有序队列合并得到的。有序队列f[i-1,v]即f[i-1,v,1..K],f[i-1,v-w[i]]+c[i]则理解为在f[i-1,v-w[i],1..K]的每个数上加上c[i]后得到的有序队列。得到这两个有序队列合并以后结果的前K项,到f[i,v,1..K]中的复杂度是。最后的答案是f[N,V,K]。总的复杂度是。

为什么这个方法正确呢?实际上,一个正确的状态转移方程的求解过程遍历了所有可用的策略,也就覆盖了问题的所有方案。只不过由于是求最优解,所以其它在任何一个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组,并在这个数组中有序的保存该状态可取到的前K个最优值。那么,对于任两个状态的max运算等价于两个由大到小的有序队列的合并。

另外还要注意题目对于“第K优解”的定义,将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者,则维护有序队列时要保证队列里的数没有重复的。

由于本题相当于求解前K个最优解的和,最终答案是f[N,V,1..K]的和。

 

小结

显然,这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包类动态规划问题与其它领域(例如数论、图论)结合起来的问题,在这篇论背包问题的专文中也不会论及。但只要深刻领会前述所有类别的背包问题的思路和状态转移方程,遇到其它的变形问法,只要题目难度还属于NOIP,应该也不难想出算法。

触类旁通、举一反三,应该也是一个OIer应有的品质吧。

 

 

【纪中】Day1

【队伍统计】
题意:在n个人中,有m条矛盾关系(u, v),表示编号为u的人想要排在编号为v的人前面。询问矛盾关系不超过k条的排列。
这题早上没有做,也没听讲,但看了眼题目感觉是深搜或者状压dp。
这里采用状压dp。用S表示当前已经排好队的状态,则f[s][k]表示当前状态违背的矛盾关系。对于一个要新加入的i,需要满足i不在排列中。设i与当前排列产生的矛盾关系为q,
那么f[s][k]则可以转移到f[s|(1 << (i - 1)) ][k + q]。暴力转移时间复杂度是O(2^n * n ^ 2 * k)。
由于矛盾关系没有重复,则可以把与i有矛盾关系的用二进制来表示。矛盾关系数便可以表示为&操作后的1个数。
T1【序列问题】
题意:给出一个序列,求每个区间的最大最小值的乘积和。
以前做过一道看上去相似的题目,先暴力预处理,再线段树修改。今天也是怎么想,但显然不对。。。
正解对序列进行分治,考虑过mid的区间[l,r]对答案的贡献。枚举右端点r,那么当右端点的指针往右移时,max增加,min减少,左端点l满足max 𝑙 = min(𝑟),则可以左移。于是,相同的max、min的贡献就可以O(1)求出。序列分治可以用递归处理。
T2【带权排序】
题意:序列A的每一个数在一个区间中随机生成,每个位置有权值si,求排序后A的期望。
期望。。。不会化!不会求!没听懂!
T3【概率博弈 】
题意:给出一颗以1为根的树,树上权值随机生成,求从根节点到叶节点的期望。
设当前要求ans > x。因为只会是向大于x或小于x的方向走,设权值 >x的为1,否则为0.相当于有m - x + 1个1,x- 1个0,则问题转化为求f[1]的概率。可用树形背包来解决。

第一天给我的感觉是题目好难,唯一看的出解的还不需要做。下午的讲题有点难懂,第一题分治方法好理解,但最关键的前缀和处理则一句跳过。第二题期望本来就不会,还要化简。第三题转化听懂了,但树形背包是什么???

Day8

【日历游戏】
题意:对一个日期有两种操作:1.跳到日历上的下一天。2.跳到日历上的下个月的同一天(如果不存在,则不能这么做)。询问先手是否必胜。
博弈论+记忆化搜索,对于先手必胜的日期,它的下一天或下个月同一天先手必败。对于先手必败的日期,其后一天或下个月先手必胜。
【二叉查找树】
题意:求将n个数加入二叉树,并使其高度恰好为h的方案数。
考虑树形dp。设f[x][h]表示有x个节点的子树,并以x为父节点,高度为h的方案数,设g[x][h]表示有x个节点的子树,并以x为父节点,高度小于等于h的方案数。
那么f[x][h] = (f[x - 1][h - 1]*f[n - x][h - 1] - g[x - 1][h - 2] * g[n - x][h - 2]) * C(x - 1, n - 1);
由于f[x - 1]的相乘会计算重复的,所以要减去重复计算的,最后的排列组合是计算将剩下的数放入x的子树中的方案数。
【我们爱数数】
题意:规定第i人坐在i - 1、i、i + 1的位置上是开心的,询问使>=k的人开心的方案数。
DFS + DP + 容斥。令f[i][j][s]表示1-i位子有j个人已经坐下且这j个人一定开心,s表示i和i+1是否坐下。首先暴力枚举初始状态,即1、2位置是否坐人,坐的人是谁。
那么f[i][j][s >> 1 ] += f[i - 1][j][s];
f[i][j][(s | (1 << d)) >> 1] += f[i - 1][j - 1][s](d=0,1,2,分别表示第i-1,i,i+1个人坐第i个位置)。
最后判断一下初态和终态是否矛盾。
设ans[n][j]表示j个人一定开心的方案(存在重复)。ans[n][j] = f[n][j][s] * (n - j)!。
因为ans中剩下的n - j不一定是不开心的,所以在统计中会出现重复的状态。
最后用容斥来求方案数。

Day3

【作文】
题意:求一个字符串的子串,使其在字符串中至少出现三次,分别是前缀、后缀、以及非前、后缀。
字符串匹配,考虑KMP,分别将字符串删去前一个字符和后一个字符,将这两个串进行匹配,求出前缀、后缀的可行长度。对原串求next数组,在可行前后缀的位置求答案。
正解是二分,哈希暴力求出前后缀的可行长度,二分这些长度暴力判断。
【智能机器人】
题意:用多个机器人遍历一棵树,使消耗的代接最小。
首先,一个明显的结论,如果从某个节点往下走去了多于1个机器人,那么它们绝对不会再回头.如果它们有一个回头,则令这个机器人处于该节点的父节点不动,令另外一个机器人先走这个机器人走的路线然后在走自己的路线,就会更优!
令f[x][i]表示i个机器人走完x子树的最优值。g[x]表示只用一个机器人走x子树(即机器人要回到x点)。可得:
f[x][i] = min(f[x][i - j] + f[y][j] + w * j)。
f[x][i] = min(g[x] + f[y][i] + w * i)。
f[x][i] = min(f[x][i] + g[y] + w * 2)。
g[x] = g[x] + g[y] + w * 2。
【大都市】
题意:给定一棵树,从1结点出发,每次修改一条边,求到某个点的路径上经过的未修改路径树。
可以发现,如果修改一条边,则这条边所连接的子树答案都会改变(-1)。联想到DFS序,在DFS序中,一个点的子树是一段连续的区间,那么,可以使用数据结构来维护修改,如树状数组,线段树。

7月17日备战Noip2017暑假集训2(A) 贝茜的晨练计划【动态规划】

晨练

【问题描述】

小 Y 打算通过锻炼来培养自己的运动细胞,他选择的运动方式是每天进行N分钟的晨跑(1<=N<=10000)。

在每分钟的开始,小 Y 会选择下一分钟是用来跑步还是休息。小 Y 的体力限制了他跑步的距离。更具体地,如果小 Y 选择在第 i 分钟内跑步,他可以在这一分钟内跑 D_i(1<=D_i<=1000)米,并且他的疲劳度会增加1。不过,无论何时小 Y 的疲劳度都不能超过 M(1 <=M<=500)。如果小 Y 选择休息,那么他的疲劳度就会每分钟减少 1,但他必须休息到疲劳度恢复到0为止。在疲劳度为 0 时休息的话,疲劳度不会再变动。晨跑开始时,小 Y 的疲劳度为 0。还有,在N分钟的锻炼结束时,小 Y 的疲劳度也必须恢复到0,否则他将没有足够的精力来对付这一整天中剩下的事情。

请你计算一下,小 Y 最多能跑多少米。

【输入格式】

第1行:2个用空格隔开的整数:n,m。

第2..n+1行:第i+1行为1个整数D_i。

【输出格式】

输出一行为一个整数,表示在满足所有限制条件的情况下,小y能跑的最大距离。

【输入样例】

5 2

5

3

4

2

10

【输出样例】

9

数据范围与约定

对于30%的数据:n<=50。

对于100%的数据:n<=10000。

继续阅读7月17日备战Noip2017暑假集训2(A) 贝茜的晨练计划【动态规划】

Day2

【曲线】
题意:令f(x)为多个二次(一次)函数的最大值,求f(x)的最小值。
画图可以发现两个二次函数取最大值的图像形状类似二次函数,可得f(x)的图像也类似二次函数。那么,可以在所给区间内用三分求出答案。
二分也可完成此题,二分答案ans,暴力判断每个二次函数<=ans的区间是否有交集,若有,则答案可行,反之答案不可行。

【挑战】

题意:将字符串分块,使每个块中的字母都在下一个块中出现过。(即下一块每个字母的出现次数比当前块多)。求最多的分块。
令f[i][j]表示在i位是最后一个块的长度为j的答案。可由f[i - j][k]转移得到。时间复杂度为O(n ^ 3)。可得70分。
改进这个算法,因为要求块最多,应用贪心的思想,每个块的长度越少,块的数量越多。令f[i]表示以i为结尾最后一块的长度最短是多少。可以由f[i - f[i]]转移得到。

【序列】

题意:判断序列的所有子序列是否都有数只出现一次。
暴力枚举每个子序列,判断是否符合条件,可得30分。
改进暴力,对于一个a[i],前一次出现记为pre[i],后一次出现记为nex[i]。那左端点l在pre[i]+1..i,右端点在i..nex[i]-1都是合法的。如果判定一个区间[l,r],a[i]是其中唯一出现过的数字。那这个区间就可以切割成判定2个区间[l,i - 1],[i + 1, r]。那对于一个区间[l,r],i,j同时从左边和右边开始扫,碰到第一个唯一出现的数字就切割。直到l>=r。
这种做法看起来很像暴力,但实际上跑得飞快。时间复杂度证明:T(n) = T(k) + T(n-k)+min(n, n - k)。一种直观的想法就是,每次复杂度都是较小的那个区间。倒过来看相当于较小的合并到较大的。那就是启发式合并。O(nlogn)。

主要代码如下:

继续阅读Day2

Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

继续阅读Day1:A+组