DP问题专题二 01背包专题

自用笔记算法

01背包巧用与强化

ACM-HDOJ 2602(01背包水题)

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

01背包水题。只是把物品变成了骨头。

参考AC代码

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int value[1050],cost[1050],dp[1050],bag,n;
		memset(dp,0,sizeof(dp));
		cin>>n>>bag;
		for(int i=1;i<=n;i++)
			cin>>value[i];
		for(int i=1;i<=n;i++)
			cin>>cost[i];
		for(int i=1;i<=n;i++)
			for(int v=bag;v>=cost[i];v--)
				dp[v]=max(dp[v],dp[v-cost[i]]+value[i]);
		cout<<dp[bag]<<endl;
	}
	return 0;
}

思路

参考DP专题一的01背包介绍，此题完全套状态方程。

注意事项

内循环逆序。

ACM-HDOJ 2639(01背包第k优解)

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

在2602题的基础上求第k优解。

参考AC代码

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
#include<cstdio>
#include<iostream>
using namespace std;
struct Node
{
	int value,cost;
}node[1005];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,k,v,dp[1005][31]={0},a[31],b[31];
		cin>>n>>v>>k;
		for(int i=1;i<=n;i++)
			cin>>node[i].value;
		for(int i=1;i<=n;i++)
			cin>>node[i].cost;
		for(int i=1;i<=n;i++)
			for(int j=v;j>=node[i].cost;j--)
			{
				for(int d=1;d<=k;d++)
				{
					a[d]=dp[j-node[i].cost][d]+node[i].value;
					b[d]=dp[j][d];
				}
				int x,y,z;
				x=y=z=1;
				int a[d]=b[d]=-1;
				while(z<=k && (a[x]!=-1 || b[y]!=-1))
				{
					if(a[x]>b[y])
						dp[j][z]=a[x++];
					else
						dp[j][z]=b[y++];
					if(dp[j][z]!=dp[j][z-1])
						z++;
				}
			}
		cout<<dp[v][k]<<endl;
	}
	return 0;
}

思路

　　对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复
杂度上多一个系数K。其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。首先看01背包求
最优解的状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。如果要求第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-c[i]]+w[i]这两
个有序队列合并得到的。有序队列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]则理解为在f[i-1][v-c[i]] [1..K]的每个数上加上w[i]后得到的有序队列.合并这两个有
序队列并将结果的前K项储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N][V][K]。总的复杂度是O(VNK)。
　　为什么这个方法正确呢？实际上，一个正确的状态转移方程的求解过程遍历了所有可用的策略，也就覆盖了问题的所有方案。只不过由于是求最优解，所以其 它在任何一
个策略上达不到最优的方案都被忽略了。如果把每个状态表示成一个大小为K的数组，并在这个数组中有序的保存该状态可取到的前K个最优值。那么， 对于任两个状态的max
运算等价于两个由大到小的有序队列的合并。另外还要注意题目对于“第K优解”的定义，将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者，则维护
有序队列时要保证队列里的数没有重复的。
　　用个形象的比喻吧：如果我想知道学年最高分，那么，我只要知道每个班级的最高分，然后统计一遍就可以了。如果我想知道学年前十呢？我必须要知道每个班的前十名。
大家在心里模拟一下，对，这就是本题核心的算法。两种决策，就可以看作这个学年只有两个班。
　　根据以上思路，将原来的dp[i]扩展成dp[i][j]表示背包容量用了i的第j优解。

注意事项

分别使用a，b两个数组存储两种状态，再合并求最大值。

ACM-HDOJ 2955(01背包巧用)

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

小偷抢银行，给出银行的个数，每个银行中的存款和每个银行中被抓的概率，求出在小于给定概率的情况下抢得的最大值。

参考AC代码

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
	int money;
	double caught;
}bank[105];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,sum=0;
		double p,dp[10005];
		cin>>p>>n;
		p=1-p;
		for(int i=0;i<n;i++)
		{
			cin>>bank[i].money>>bank[i].caught;
			bank[i].caught=1-bank[i].caught;
			sum+=bank[i].money;
		}
		memset(dp,0.0,sizeof(dp));
		dp[0]=1.0;
		for(int i=0;i<n;i++)
			for(int j=sum;j>=bank[i].money;j--)
				dp[j]=max(dp[j],dp[j-bank[i].money]*bank[i].caught);
		for(int i=sum;i>=0;i--)
			if(dp[i]>p)
			{
				cout<<i<<endl;
				break;
			}
	}
	return 0;
}

思路

1、抢n个银行，不被抓，是每次都不被抓，用乘法原理处理每次不被抓的概率。
2、转化为01背包：将所有银行的总钱数当做背包的容积v，将不被抓的概率当做cost[i]，
在一般的01背包中都是加上cost[i] ，这里由于是乘法原理，所以应该是转化为乘法。
这样，传统的01背包累加问题变成了垒乘。
3、状态转移方程：dp[j]=max(dp[j],dp[j-bank[i].money]*bank[i].caught)
dp[j]表示抢j钱时的最大不被抓概率。

注意事项

此题乍看与背包问题无关，其实是变相的01背包问题。由于dp求得的是最大的不被抓概率，所以程序中的p和bank[i].caught必须转化为不被抓的概率，即用1减去本身。
最后在判断的时候需注意i从sum开始，即从最大背包容量开始判断，每个容量对应的最大不被抓概率是否满足小于给定的概率，若满足则立刻输出并结束循环，保证输出
的是最优化值。dp的初始化也要注意给dp[0]赋为1，因为当抢钱数为0是不会被抓。

ACM-HDOJ 3466(01背包排序)

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

用钱买商品，每件物品只有在大于特定资金才能进行交易，在总资金一定的情况下求获得的最大价值。

参考AC代码

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
	int p,q,v,cha;
}a[550];
int cmp(node A,node B)
{
	return A.cha<B.cha;
}
int main()
{
	int n,m,dp[5050];
	while(cin>>n>>m)
	{
		for(int i=0;i<n;i++)
		{
			cin>>a[i].p>>a[i].q>>a[i].v;
			a[i].cha=a[i].q-a[i].p;
		}
		memset(dp,0,sizeof(dp));
		sort(a,a+n,cmp);
		for(int i=0;i<n;i++)
			for(int j=m;j>=a[i].q;j--)
				dp[j]=max(dp[j],dp[j-a[i].p]+a[i].v);
		cout<<dp[m]<<endl;
	}
	return 0;
}

思路

此道01背包问题需要sort排序，理由如下：
有两个物品(p1,q1,v1),(p2,q2,v2)，然后物品1先放的话，物品2就可以借助物品1产生的各种状态来进行下一步转移，而如果物品2的q2值过高，在这个[q2,m]的区间内都
不存在物品1造成的新状态的话，那么物品1的状态就没有得到利用。而如果交换顺序，先放了物品2，那么显然物品1就可以利用物品2产生的新状态。
所以物品1能从物品2转移的状态区间其实是[min(q1+p2,m),m]，物品2能从物品1转移的状态区间是[min(q2+p1,m),m]。所以尽可能地复用这个区间，让区间小的先来，
区间大的后来，这样排序之后所有物品都能从前面的物品得到新状态进行转移。
先买A，至少需要p1+q2，先买B，至少需要p2+q1;若A q2-p2;即差值大的先买，所以先买的应排到后面。
而普通的01背包之所以不需要排序,是因为p1==q1,p2==q2,排序跟不排是一回事。这一类的dp题要注意后效性是否存在，如果存在通过改变顺序之类的办法来取消后效性。
在ACM-HDOJ 2546题中，qi恒定为5，所以也是需要排序的。

注意事项

因为01背包的内循环是逆序，所以在先买差值大的情况下，a数组应从小到大进行排列，确保在循环中先从末尾的最大买起。

ACM-HDOJ 1864(01背包变形)

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

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
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[3000050];
int main()
{
	int money[31],fund2;
	int num1,num2;
	double sum1,fund;
	char ch;
	while(scanf("%lf%d",&sum1,&num1)&&num1)
	{
		int sum=int(sum1*100);
		memset(money,0,sizeof(money));
		memset(dp,0,sizeof(dp));
		int l=0;
		for(int i=0;i<num1;i++)
		{
			scanf("%d",&num2);
			int a=0,b=0,c=0,flag=1;
			while(num2--)
			{
				scanf(" %c:%lf",&ch,&fund);
				fund2=int(fund*100);
				if(ch=='A'&&a+fund2<=60000)
					a+=fund2;
				else if(ch=='B'&&b+fund2<=60000)
					b+=fund2;
				else if(ch=='C'&&c+fund2<=60000)
					c+=fund2;
				else
					flag=0;
			}
			if(a+b+c<=100000 && a<=60000 && b<=60000 && c<=60000 && flag)
				money[l++]=a+b+c;
		}
		for(int i=0;i<=l;i++)
			for(int j=sum;j>=money[i];j--)
				dp[j]=max(dp[j],dp[j-money[i]]+money[i]);
		printf("%.2lf\n",dp[sum]/100.0);
	}
	return 0;
}

思路

依次搜索每张发票的信息，判断是否满足题给的三个条件：只有ABC三类，ABC单项小于600，ABC和小于1000.若均满足后存入money数组，之后对该数组进行01背包的
操作后即可得出结果。

注意事项

由于该题要求有关数据均要保留两位小数，所以为了简化操作，把所有的小数均扩大100倍后进行整型操作，最后只需要把结果在除以100.0即可。注意l的定义要在for循环之
外，因为money数组存放的是所有满足条件发票的总资金。只要有一个不是ABC类型的flag=0，不满足if判断直接进行下一张发票的判断。dp数组应该开到30×1000×100的
大小，防止数组越界。(多乘的100是因为扩大了100倍)

本文标题:DP问题专题二 01背包专题

文章作者:Hippopmonkey

发布时间:2016-08-30, 22:08:10

最后更新:2016-08-30, 22:18:59

原始链接:http://xuboming8.github.io/2016/08/30/DP问题专题二-01背包专题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 01背包巧用与强化
    1. 1.1. ACM-HDOJ 2602(01背包水题)
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
      4. 1.1.4. 注意事项
    2. 1.2. ACM-HDOJ 2639(01背包第k优解)
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
      4. 1.2.4. 注意事项
    3. 1.3. ACM-HDOJ 2955(01背包巧用)
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
      4. 1.3.4. 注意事项
    4. 1.4. ACM-HDOJ 3466(01背包排序)
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
      4. 1.4.4. 注意事项
    5. 1.5. ACM-HDOJ 1864(01背包变形)
      1. 1.5.1. 参考AC代码
      2. 1.5.2. 思路
      3. 1.5.3. 注意事项
|