标签归档:动态规划

小飞侠的游园方案

问题描述
经过抽签选择,小智将军第一个进入考场。
  菜虫:(身上散射出华贵(?)的光芒)欢迎你,第一位挑战者!!
  小智:……(走到菜虫身后,关灯)女王陛下,虽然我们国家现在很富裕,但也请您不要浪费电来用这么大功率的灯泡。
  菜虫(汗):啊啊~~爱卿所言甚是~~那么,你的题目是……我们的情报组织探听到敌人的重要将领——小飞侠星期天会邀他的灵儿妹妹到公园去玩。公园里有很多娱乐项目,可并不是每一项他们都喜欢,所以他们对每一项都进行了“喜欢度”的评分。因为小飞侠也是一个了不起的角色,所以他一定会选择在有限时间内的最好的方案。现在要你做的就是找出在规定时间内他们选择哪几项不同的活动可以使其“喜欢度”之和达到最大,据此我们就可以知道他会在哪些地方出现,从而在那里派人看守了。

  小智:(灯泡一亮)每个地方都派人看守不就行了?!
  “当~~~”
  菜虫:(手执八公分直径炒锅,筋)……你是白痴吗?-_-##(都派人去看守的话我们会有多少桌三缺一?!)听好了,输入格式是第一行一个正整数N(1<=N<=100)表示总共的娱乐项目数;第二行一个正整数表示规定的时间t(0样例输入 Sample Input
3
5
1 2
5 5
4 3

样例输出 Sample Output
5

算法分析
简单的动态规划

0/1 背包

f[i,j]:=max{f[i-1,j], f[i-1,j-t[i]]+a[i]}

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <string.h>
#define max(a,b)a>b?a:b
int main()
{
       int n, m, i, j;
       int b[101][1001];
       int time[101], like[101];
 
       scanf("%d%d", &n, &m);
       for (i = 1; i <= n; i++)
       {
              scanf("%d%d", &like[i], &time[i]);
       }
 
       memset(b, 0, sizeof(int) * 101 * 1001);
 
       for ( i = 1; i <= n; i++)
       {
              for (j = 1; j <= m; j++)
              {
                     if (time[i] > j)
                            b[i][j] = b[i - 1][j];
                     else
                            b[i][j] = max(b[i - 1][j], b[i - 1][j - time[i]] + like[i]);
              }
       }
       printf("%ld\n", b[n][m]);
       return 0;
}

暗黑破坏神

[问题描述]
无聊中的小x玩起了Diablo I… 游戏的主人公有n个魔法每个魔法分为若干个等级,第i个魔法有p[i]个等级(不包括0)。每个魔法的每个等级都有一个效果值,一个j级的i种魔法的效果值为w[i][j] 。魔法升一级需要一本相应的魔法书购买魔法书需要金币,第i个魔法的魔法书价格为c[i],而小x只有m个金币(好孩子不用修改器),你的任务就是帮助小x决定如何购买魔法书才能使所有魔法的效果值之和最大,开始时所有魔法为0级 效果值为0

Input
第一行 用空格隔开的两个整数n m ,以下n行 描述n个魔法,第i+1行描述 第i个魔法 格式如下 :c[i] p[i] w[i][1] w[i][2] … w[i][p[i]]

Output
第一行输出一个整数,即最大效果值。 以后n行输出你的方案:
第i+1行有一个整数v[i] 表示你决定把第i个魔法学到v[i]级
如果有多解 输出花费金币最少的一组
如果还多解 输出任意一组

Sample Input
3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10

Sample Output
11
1
0
3

Hint

数据范围:
0 < n <= 100 0 < m <= 500 0 < p[i] <= 50 0 < c[i] <= 10 算法描述:动态规划。 F[i][j] 表示前i个魔法使用j个金币可以达到的最大的效果。 状态转移方程: f[i][j] = max(f[i – 1][j], f[i – 1][j – k * c[i]] + w[i][k]) 1 <= k <= p[i] 并且j >= k * c[i]
对于第i个魔法,它可以不升级(也就是保持0级),同样也可以达到1到p[i]的级。然而要达到第k级的魔法,所要消耗的金币数是k*c[i],而金币数为j,所以状态转移方程就如上所示。最后还要使用一个二维数组存取这个最大值的时候这个魔法所要达到的级数。为后面的级数输出做准备。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <string.h>
#define max(a,b) a>b?a:b
int f[101][501], mark[101][501], p[101],  c[101], w[101][51], v[101];
int main()
{
	int n, m, i, j, k, max, t;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++)
	{
		scanf("%d%d", &c[i], &p[i]);
		for (j = 1; j <= p[i]; j++)
			scanf("%d", &w[i][j]);
	}
	memset(f, 0, sizeof(f));
	for (i = 1; i <= n; i++) //对于每个魔法
	{
		for (j = 1; j <= m; j++)//当使用j个金币时
		{
			f[i][j] = f[i - 1][j];//不升级
			mark[i][j] = 0;//记录标记
			for (k = 1; k <= p[i]; k++)//对于每个级数
			{
				if (j >= k * c[i])//如果金币够用的话
				{
					if (f[i - 1][j - k * c[i]] + w[i][k] > f[i][j])//寻找最大的效果,并记录下来
					{
						f[i][j] = f[i - 1][j - k * c[i]] + w[i][k];
						mark[i][j] = k;
					}
				}
				else
					break;
			}
		}
	}
	max = 0;
	for (j = m; j >= 1; j--)//寻找花费金币最少,而效果最大的那个解
	{
		for (i = n; i >= 1; i--)
		{
			if (f[i][j] >= max)
			{
				k = j;
				t = i;
				max = f[i][j];
			}
		}
	}
	memset(v, 0, sizeof(v));
	j = k;//从后往前找出每个魔法所要达到的级数。
	for (i = t; i >= 1; i--)
	{
		v[i] = mark[i][j];
		j = j - c[i] * v[i];
	}
	printf("%d\n", max);
	for (i = 1; i <= n; i++)
		printf("%d\n", v[i]);
	return 0;
}

选课(Tree dynamic)

问题描述
学校实行学分制。每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。学校开设了N(N<300)门的选修课程,每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。   在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号,依次为1,2,3,…。 例如:表中1是2的先修课,2是3、4的先修课。如果要选3,那么1和2都一定已被选修过。 你的任务是为自己确定一个选课方案,使得你能得到的学分最多,并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。 输入格式 Input Format
输入文件的第一行包括两个整数N、M(中间用一个空格隔开)其中1≤N≤300,1≤M≤N。

以下N行每行代表一门课。课号依次为1,2,…,N。每行有两个数(用一个空格隔开),第一个数为这门课先修课的课号(若不存在先修课则该项为0),第二个数为这门课的学分。学分是不超过10的正整数。

输出格式 Output Format
输出文件只有一个数,实际所选课程的学分总数。

样例输入 Sample Input
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

样例输出 Sample Output
13

注释 Hint

算法分析
典型树型DP

有两种方法:
1.构建一颗多叉树,父结点选了才能选子结点,递归调用和指针.
2.将多叉树转化为2叉树(左儿子右兄弟),左儿子必须要有父结点而右儿子不必,递归调用和数组记录.
这里讲第一种:
f[i,j]表示第i个结点为根最多选j个课时得到的最大学分.
初值f[i,j]:=score[i];

对于一个父结点x,它有num个子结点,为son[i].用类似背包的方式处理子结点的加分.则
f[x,j]:=max{f[x,j],f[x,k]+f[son[i],j-k]} 2<=j<=m,0<=i<=num;1<=k<=j 注意对于一开始的输入m应该加1,因为需要设置一个根为0   树型DP。 将N叉树转化成二叉树,在建树过程中就将其转化。 tree[i,j]=max{tree[tree[i].right,j],tree[tree[i].left,k-1]+tree[tree[i].right,y-k]+tree[i].data}    {0<=i<=n,2<=j<=m,1<=k<=j} 原本是多叉树,将它转变成二叉树。如果两节点a,b同为兄弟,则将b设为a的右节点;如果节点b是节点a的儿子,则将节点b设为a的左节点。 【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
 
#define MAXN 501
typedef struct node
{
       int mark;
       int l, r;
}tree;
 
tree a[MAXN];
int f[MAXN][MAXN], lastkid[MAXN];
void dp(int i, int j);
int main()
{
       int n, m, i, pre;
       scanf("%d%d", &n, &m);
       memset(a, 0, sizeof(a));
       memset(lastkid, 0, sizeof(lastkid));
 
       for (i = 0; i <= n; i++)
       {
              a[i].l = a[i].r = a[i].mark = 0;
              lastkid[i] = 0;
       }
 
       for (i = 1; i <= n; i++)
       {
              scanf("%d%d", &pre, &a[i].mark);
              if (lastkid[pre] == 0)     //没有兄弟结点,则成为pre的左子树
              {
                     lastkid[pre] = i;
                     a[pre].l = i; 
              }
              else                              //有兄弟结点,成为兄弟结点的右子树
              {
                     a[lastkid[pre]].r = i;
                     lastkid[pre] = i;
              }
       }
 
       for (i = 1; i <= m; i++)  
              dp(a[0].l, i);
 
       printf("%d\n", f[a[0].l][m]);
       return 0;
 
}
 
void dp(int i, int j)
{
       int k;
       if (a[i].l != 0) dp(a[i].l, j);    //切记,一定要先求其孩子的
       if (a[i].r != 0) dp(a[i].r, j);
       f[i][j] = a[i].mark; 
       if (a[i].l != 0 || a[i].r != 0)
       {
              for (k = 1; k <= j; k++)
                     if (f[i][j] < (f[a[i].l][k - 1] + f[a[i].r][j - k] + a[i].mark))
                            f[i][j] = f[a[i].l][k - 1] + f[a[i].r][j - k] + a[i].mark;
       }
 
       if (f[i][j] < f[a[i].r][j])
              f[i][j] = f[a[i].r][j];
}