DP问题专题四 背包延伸

自用笔记算法

分组背包 混合背包 二维背包

ACM-HDOJ 1712(分组背包)

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
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[105],m,matrix[105][105];
void GroupedPack(int x)
{
	for(int i=m;i>0;i--)
		for(int j=i;j>0;j--)
			dp[i]=max(dp[i],dp[i-j]+matrix[x][j]);
}
int main()
{
	int n;
	while(cin>>n>>m)
	{
		if(n==0&&m==0)
			break;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>matrix[i][j];
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
			GroupedPack(i);
		cout<<dp[m]<<endl;
	}
	return 0;
}

思路

由于每门课复习不同的天数有不同的成效，所以用分组背包来求解。在一般背包的基础上多加一层for循环来判断每种物品不同的价值即可。

注意事项

第三个for循环中的j必须从i开始递减至0，因为每门课花费的天数必须少于给定的总天数。

ACM-HDOJ 3591(混合背包)

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

小倩去超市买东西。第一行给出两个数据表示她带有的硬币数目和需要买的商品的总资金，下面n行代表硬币的面额和数量。买完商品如果给出的钱超出了总价值，那么收
银员会找对应的钱。小倩给出的钱最多为2w，已知收银员的硬币无数，求小倩买商品的硬币和收银员找零的硬币和的最小数量。

参考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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define m 20000
#define Inf 0x7FFFFFF
using namespace std;
struct node
{
	int num,value;
}coin[250];
int dp1[m+5],dp2[m+5],n;
void ZeroOnePack(int dp[],int value,int weight)
{
	for(int v=m;v>=value;v--)
		dp[v]=min(dp[v],dp[v-value]+weight);
}
void CompletePack(int dp[],int value)
{
	for(int v=value;v<=m;v++)
		dp[v]=min(dp[v],dp[v-value]+1);
}
void MultiPack(int dp[],int value,int amount)
{
	if(value*amount>=m)
	{
		CompletePack(dp,value);
		return;
	}
	for(int k=1;k<amount;k*=2)
	{
		ZeroOnePack(dp,k*value,k);
		amount-=k;
	}
	ZeroOnePack(dp,amount*value,amount);
}
int main()
{
	int n,t,flag=1;
	while(cin>>n>>t)
	{
		if(n==0&&t==0)
			break;
		for(int i=1;i<=n;i++)
			cin>>coin[i].value;
		for(int i=1;i<=n;i++)
			cin>>coin[i].num;
		for(int i=1;i<=m;i++)
			dp1[i]=dp2[i]=Inf;
		dp1[0]=dp2[0]=0;
		for(int i=1;i<=n;i++)
		{
			MultiPack(dp1,coin[i].value,coin[i].num);
			CompletePack(dp2,coin[i].value);
		}
		int ans=dp1[t];
		for(int i=t+1;i<=20000;i++)
			ans=min(ans,dp1[i]+dp2[i-t]);
		if(ans==Inf)
			cout<<"Case "<<flag++<<": -1"<<endl;
		else
			cout<<"Case "<<flag++<<": "<<ans<<endl;
	}
	return 0;
}

思路

完全背包+多重背包：由于小倩买东西的时候给出的商品数量已知，所以是多重背包问题。收银员找钱的时候由于硬币无数，所以是完全背包问题。定义2个数组dp1和dp2
分别记录2种背包的状态。由于求的是最小数量，所以两个dp数组初始化为Inf，dp[0]初始化为0.带入模版求完后求出最小值。注意dp1[i]与dp2[i-t]即可(i是小倩付的钱).

注意事项

由于此题求的是最小数量而不是最小价值，所以原本的多重背包的模版应稍作调整。max函数换成min，删去原本模版中的weight(硬币的数量都是一个一个的放入背包中)，
01背包背包中状态方程中min的第二项的后面应加weight而完全背包中应加1，理由如下：01背包中使用了二进制优化，所以k带入01背包后由于修改了面纸，对应面纸的
硬币原本的数量已经不为1，所以需要加上weight(k),而完全背包中是严格的一个硬币对应原本的面纸，所以min中第二项只需加1即可，无需引入weight变量。

ACM-HDOJ 2159(二维完全背包)

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
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
	int value,weight;
}a[105];
int dp[105][105];
int main()
{
	int n,m,k,s,i;
	while(cin>>n>>m>>k>>s)
	{
		for(int i=1;i<=k;i++)
			cin>>a[i].value>>a[i].weight;
		memset(dp,0,sizeof(dp));
		for(i=1;i<=m;i++)
		{
			for(int j=1;j<=k;j++)
				for(int w=1;w<=s;w++)
					if(a[j].weight<=i)
						dp[i][w]=max(dp[i][w],dp[i-a[j].weight][w-1]+a[j].value);
			if(dp[i][s]>=n)
				break;
		}
		if(i>m)
			cout<<"-1"<<endl;
		else
			cout<<m-i<<endl;
	}
	return 0;
}

思路

dp[i][k]表示在i忍耐度下杀k只怪所得到的最多经验，状态转移方程为:dp[i][k]=max(dp[i][k],dp[i-a[j].w][k-1]+a[j].v)。三个for循环分别表示忍耐度，怪物的种类以
及怪物的最大击杀量(从w=1开始实际就表示为击杀量)，并且在使用状态方程前应判断该种类的怪物消耗的忍耐度要小于人持有的忍耐度。若当前获得的经验已经可以升级，
那么立即退出循环，此时的i就是使用掉的忍耐度。如果i大于总忍耐度m那么输出-1，否则输出m-i(剩下的最大忍耐度)。

注意事项

此问题的实质依然为完全背包，要正确理解三个for循环的顺序与意义，第一个for循环于忍耐度有关，剩下2个for循环与怪物有关。并且在使用状态方程前一定要判断该种类
怪物的忍耐度是够小于人的总忍耐度。

ACM-HDOJ 3496(二维01背包)

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

要求在N盘DVD中选出M盘，每盘DVD都有对应的耗时和价值，要求在耗时小于l的情况下求出看完M盘DVD所获得的最大价值。

参考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<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#define Inf 0x7FFFFFF
using namespace std;
struct node
{
	int value,cost;
}a[105];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m,l;
		int dp[105][1005];
		cin>>n>>m>>l;
		for(int i=1;i<=n;i++)
			cin>>a[i].cost>>a[i].value;
		for(int i=0;i<=m;i++)
			for(int j=0;j<=l;j++)
			{
				if(i==0)
					dp[i][j]=0;
				else
					dp[i][j]=-Inf;
			}
		for(int i=1;i<=n;i++)
			for(int j=m;j>=1;j--)
				for(int k=l;k>=a[i].cost;k--)
					dp[j][k]=max(dp[j][k],dp[j-1][k-a[i].cost]+a[i].value);
		if(dp[m][l]>0)
			cout<<dp[m][l]<<endl;
		else
			cout<<"0"<<endl;
	}
	return 0;
}

思路

01背包的模型，但由于有DVD光盘数限制和时间限制2个条件，所以使用二维数组求解。dp[i][k]表示看完i盘DVD且耗时k的情况下获得的最大价值。dp的初始化需要把第一
行赋值为0，其余为-Inf。三个for循环分别代表总光盘数，看的光盘数和耗时(逆序)，如果价值小于0则输出0.

注意事项

由于此题存在价值为负的情况，所以最后dp求出的值若为负数则要输出0。另外dp数组的初始化也要额外注意，因为价值有负，所以dp数组的第一行需要初始化为0，其余
复制为-Inf。dp数组的初始化要从0开始。

本文标题:DP问题专题四 背包延伸

文章作者:Hippopmonkey

发布时间:2016-08-30, 22:47:33

最后更新:2016-08-30, 23:30:46

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

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

文章目录
  1. 1. 分组背包 混合背包 二维背包
    1. 1.1. ACM-HDOJ 1712(分组背包)
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
      4. 1.1.4. 注意事项
    2. 1.2. ACM-HDOJ 3591(混合背包)
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
      4. 1.2.4. 注意事项
    3. 1.3. ACM-HDOJ 2159(二维完全背包)
      1. 1.3.1. 参考AC代码
      2. 1.3.2. 思路
      3. 1.3.3. 注意事项
    4. 1.4. ACM-HDOJ 3496(二维01背包)
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
      4. 1.4.4. 注意事项
|