一、背包问题

1、Wikioi 1014 装箱问题

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

一个整数v，表示箱子容量

一个整数n，表示有n个物品

接下来n个整数，分别表示这n 个物品的各自体积

一个整数，表示箱子剩余空间。

24

6

8

3

12

7

9

7

0

一道经典的背包动规，用数组f[]进行动规，f[v]=剩余容量为v时可以利用的最大体积，那么可以在每次输入一个物品体积cost时遍历剩余容量状态，当前状态的剩余容量为v时，可以选择装入物品(装入物品则当前状态可以利用的体积为f[v-cost]+cost)或不装入物品,推出动规方程:f[v]=max{f[v-cost]+cost}

#include <stdio.h>#include <string.h>#define MAXN 30000int f[MAXN]; //f[i]=剩余体积为i时装入物品的最大体积int max(int a,int b){	if(a>b) return a;	return b;}int main(){	int v,n,cost;	scanf("%d%d",&v,&n);	for(int i=1;i<=n;i++) 	{		scanf("%d",&cost);		for(int j=v;j>=cost;j--)			f[j]=max(f[j],f[j-cost]+cost);	}	printf("%d\n",v-f[v]);	return 0;}

2、Wikioi 1068 乌龟棋

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一 的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

…… 1 2 3 4 5 ……N 乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型 的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡 片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择 一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。 游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到 该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的 分数总和。 很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡 片使用顺序使得最终游戏得分最多。 现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到 多少分吗？

输入的每行中两个数之间用一个空格隔开。 第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。 第2行N个非负整数，a1a2……aN

，其中ai表示棋盘第i个格子上的分数。 第3行M个整数，b1b2……bM

，表示M张爬行卡片上的数字。 输入数据保证到达终点时刚好用光M张爬行卡片，即N - 1=∑(1->M) b_i

输出一行一个整数

13 8

4 96 10 64 55 13 94 53 5 24 89 8 30

1 1 1 1 1 2 4 1

455

【数据范围】

对于30%的数据有1 ≤ N≤ 30，1 ≤M≤ 12。

对于50%的数据有1 ≤ N≤ 120，1 ≤M≤ 50，且4 种爬行卡片，每种卡片的张数不会超

过20。

对于100%的数据有1 ≤ N≤ 350，1 ≤M≤ 120，且4 种爬行卡片，每种卡片的张数不会

超过40；0 ≤ ai ≤ 100，1 ≤ i ≤ N；1 ≤ bi ≤ 4，1 ≤ i ≤M。输入数据保证N?1=ΣM

i b

1

可以说这是一道背包的变形题，不再是只有单一的状态(剩余体积)，实际上因为卡片分种类，导致状态变成了4个：4种爬行卡片分别剩余的张数，则可用数组f[][][][]来进行动规，f[i][j][k][h]=1、2、3、4号卡片各用掉i,j,k,h张时，下棋获得的最大分数，则每次从小到大动规，经过状态f[i][j][k][h]时，考虑用掉一张1或2或3或4号卡片，那么这次操作之前得到的分数就是f[i-1][k][j][h]或f[i][k-1][j][h]或f[i][k][j-1][h]或f[i][k][j][h-1](注：上次操作得到的分数并不包含上次操作后到达的格子分数)，然后再加上上次操作后到达的格子分数，这次操作到达的格子分数就等到下次操作时再算。最后输出f[card[1]][card[2]][card[3]][card[4]]+map[n],card[x]=第x种卡片的张数，map[n]=终点的分数。

当然也可以先算上起点的格子分数，每次决策时不加上次操作到达的格子分数，而是加上本次操作到达的格子分数，或许更便于理解

#include <stdio.h>#include <string.h>#define MAXM 40#define MAXN 400int f[MAXM][MAXM][MAXM][MAXM]; //f[i][j][k][h]=1 2 3 4四种卡片各用了i,j,k,h张时的最高分数int map[MAXN]; //棋盘上的分数int max(int a,int b){	if(a>b) return a;	return b;}int main(){	int n,m;	int card[5]={0};	scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++)		scanf("%d",&map[i]);	for(int i=0;i<m;i++)	{		int kind;		scanf("%d",&kind);		card[kind]++;	}	for(int i=0;i<=card[1];i++)		for(int j=0;j<=card[2];j++)			for(int k=0;k<=card[3];k++)				for(int h=0;h<=card[4];h++)				{					int dis=i*1+j*2+k*3+h*4; //dis=当前用了i,j,k,h张牌后乌龟棋移动的距离					if(i>=1) f[i][j][k][h]=max(f[i][j][k][h],f[i-1][j][k][h]+map[1+(i-1)*1+j*2+k*3+h*4]);					if(j>=1) f[i][j][k][h]=max(f[i][j][k][h],f[i][j-1][k][h]+map[1+i*1+(j-1)*2+k*3+h*4]);					if(k>=1) f[i][j][k][h]=max(f[i][j][k][h],f[i][j][k-1][h]+map[1+i*1+j*2+(k-1)*3+h*4]);					if(h>=1) f[i][j][k][h]=max(f[i][j][k][h],f[i][j][k][h-1]+map[1+i*1+j*2+k*3+(h-1)*4]);				}	printf("%d\n",f[card[1]][card[2]][card[3]][card[4]]+map[n]);	return 0;}

3、Wikioi 1044 拦截导弹

    某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

  

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）

  

输出这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

389 207 155 300 299 170 158 65 

6

2

导弹的高度<=30000，导弹个数<=20

可以把导弹的高度化为一个数字序列，由题意可知，一个导弹拦截的目标必为原序列的不上升子序列，要想让拦截目标个数尽量多，就要求这个不上升子序列是最长的，换句话说，第一问就是求不上升子序列，第二问略微麻烦点，要让所有目标都被打而且导弹尽量少，那么需要每个导弹不光打一个目标，而且要把以这个目标为头的不上升子序列都打到，如图，绿色的线就是不上升子序列，红色的线是严格上升子序列，很明显，第二问要求最长严格上升子序列，这个子序列中的所有元素都需要一发导弹，而它们连接的不上升子序列都能被这些导弹打到，第二问的答案就是最长严格上升子序列。

#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAXN 1000int up[MAXN],dn[MAXN];int high[MAXN],cnt=0;int maxDN=-1,maxUP=-1;int max(int a,int b){	if(a>b) return a;	return b;}int main(){	while(scanf("%d",&high[++cnt])!=EOF);	for(int i=1;i<=cnt;i++)		for(int j=1;j<i;j++)		{			if(high[i]>high[j])			{				up[i]=max(up[i],up[j]+1);			}			if(high[i]<=high[j])			{				dn[i]=max(dn[i],dn[j]+1);			}		}	for(int i=1;i<=cnt;i++)	{		maxDN=max(maxDN,dn[i]);		maxUP=max(maxUP,up[i]);	}	printf("%d\n%d\n",maxDN,maxUP+1);	return 0;}

[NOIP复习]第二章：动态规划