DP问题专题一(Dynamic Programming) 背包入门

自用笔记算法

经典DP 背包问题

三种基本背包问题的概念

01背包(Zero one pack)：
有N件物品和一个容量为V的背包， 每种物品均只有一件。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
完全背包(Complete Pack)：
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，
且价值总和最大。
多重背包(Multiple Pack)：
有N种物品和一个容量为V的背包，第i种物品最多有n[i]件可用。每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且
价值总和最大。

01背包

1背包（ZeroOnePack）: 有N件物品和一个容量为V的背包，每种物品均只有一件。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
其状态转移方程是：




把这个过程理解下：
在前i件物品放进容量v的背包时，它有两种情况




PS：第二种是如果第i件放进去，那么在容量v-c[i]里就要放进前i-1件物品
最后比较第一种与第二种所得价值的大小，哪种相对大，f[i][v]的值就是哪种。
这里是用二维数组存储的，可以把空间优化，用一维数组存储。
代码如下：(外循环正序 内循环逆序 使f[v]和f[v-c[i]]+w[i]表示前一状态的价值)
1
2
3
for i=1..N
   for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]}

完全背包

完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费
用总和不超过背包容量，且价值总和最大。
完全背包按其思路仍然可以用一个二维数组来写出：（两种状态方程）






同样的它也可以用一维数组来表示
代码如下：(外循环和内循环均正序 保证使f[v]和f[v-c[i]]+w[i]表示当前状态的价值)
1
2
3
for i=1..N
    for v=0..V
        f[v]=max{f[v],f[v-c[i]]+w[i]}

多重背包

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和
不超过背包容量，且价值总和最大。
其状态转移方程是：




多重背包问题可以转化为01背包问题：(提供如下模版)
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
void ZeroOnePack(int value,int weight)  
{  
    for(int v=m;v>=value;v--)  
        dp[v]=max(dp[v-value]+weight,dp[v]);  
}  
void CompletePack(int value,int weight)  
{  
    for(int v=value;v<=m;v++)  
        dp[v]=max(dp[v],dp[v-value]+weight);  
}  
void MultiPack(int value,int weight,int amount)  
{  
    if(value*amount>=m)  
    {  
        CompletePack(value,weight);  
        return ;  
    }  
    for(int k=1;k<amount;k*=2)  
    {  
        ZeroOnePack(k*value,k*weight);  
        amount-=k;  
    }  
    ZeroOnePack(amount*value,amount*weight);  
}
value表示每件的花费 weight表示每件的价值 amount表示每件可取的数量 m表示最大背包容量
具体在1059题中使用

也可变形为以下模版，性质不变：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void ZeroOnePack(int value,int cost)  
{  
    for(int v=m;v>=cost;v--)  
        dp[v]=max(dp[v-value]+cost,dp[v]);  
}  
void CompletePack(int value,int cost)  
{  
    for(int v=cost;v<=m;v++)  
        dp[v]=max(dp[v],dp[v-value]+cost);  
}  
void MultiPack(int value,int cost,int amount)  
{  
    if(value*amount>=m)  
    {  
        CompletePack(value,cost);  
        return ;  
    }  
    for(int k=1;k<amount;k*=2)  
    {  
        ZeroOnePack(k*value,k*cost);  
        amount-=k;  
    }  
    ZeroOnePack(amount*value,amount*cost);  
}

二进制优化

假如给了我们价值为2，数量是10的物品，我们应该把10给拆开，首先算出2^0=1,2^1=2,2^2=4,2^3=8。好了那么现在，1+2+4=7<10,1+2+4+8=15>10,所以剩下
的数字应为10-7=3。最后组成10的数字就求得为1，2，4，3。由这4个数字可以表示1-10里的任意一个数，所以这批物品就可以表示为价值为2，4，6，8的四种货物，总价
值依然为20，问题就得到了简化。

二维划为一维数组的正逆序问题

鉴于上面的分析，在01背包中应采取逆序遍历，而在完全背包中应采取正向遍历，原因参考下列博客：
由于该博主已经十分详细的分析了，这里就不在赘述
但上篇博客未牵涉到完全背包问题，所以做如下补充：
想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，
保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加
选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的
道理。

ACM-HDOJ 2546(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<algorithm>
using namespace std;
int cmp(int a,int b)
{
	return a<b;
}
int main()
{
	int n;
	while(cin>>n && n!=0)
	{
		int price[1050]={0},m,dp[1050]={0};
		for(int i=1;i<=n;i++)
			cin>>price[i];
		cin>>m;
		if(m<5)
		{
			cout<<m<<endl;
			continue;
		}
		sort(price+1,price+1+n,cmp);
		int Max=price[n];
		m-=5;
		for(int i=1;i<n;i++)
			for(int j=m;j>=price[i];j--)
				dp[j]=max(dp[j],dp[j-price[i]]+price[i]);
		cout<<(m-dp[m])+(5-Max)<<endl;
	}
	return 0;
}

思路

典型的01背包问题。但在使用状态方程前应先做如下操作：由于卡里的余额必须要大于5，所以可以做先拿5元买最贵的菜，接着卡里剩余m-5使用01背包问题求出最大价
值（这是逆向思维，若换成正序的情形更容易理解，相当于先买除了最贵以外的菜，确保买完后卡里的钱大于5元而且最少，最接近5元，接着用这5元去买最贵的菜，卡
里剩下的负值就是最小的余额）。

注意事项

虽然题目类型是典型的01背包问题，但是不代表可以直接使用状态方程求解，在经过一系列的操作后才可以使用。如本题在使用状态方程前需先用5元去买最贵的物品。
至于为什么要排序，详见DP专题二————ACM-HDOJ 3466题思路

ACM-HDOJ 1963(完全背包)

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
#include<cstdio>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
	int cost,reward;
}a[20];
int dp[1000];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int sum,year,n;
		cin>>sum>>year;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].cost>>a[i].reward;
			a[i].cost/=1000;
		}
		for(int i=1;i<=year;i++)
		{
			int s=sum/1000;
			memset(dp,0,sizeof(dp));
			for(int j=1;j<=n;j++)
				for(int k=a[j].cost;k<=s;k++)
					dp[k]=max(dp[k],dp[k-a[j].cost]+a[j].reward);
			sum+=dp[s];
		}
		cout<<sum<<endl;
	}
	return 0;
}

思路

因为每种物品可以进行多次购买，所以可以看作完全背包问题。但是要注意的是，由于本金可能会很大，所以我们要对背包的大小进行压缩，值得注意的是，题目已经说了本
金与物品的购买价格都是1000的倍数，所以我们可以将他们都除以1000来进行压缩，然后就是一道完全背包模板题了。

注意事项

要对背包的大小进行压缩。

ACM-HDOJ 1059(多重背包)

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

有一堆钻石，有6种不同的价值（1…6），现在告诉你每种的数量，问你能不能把这堆钻石按总的价值平均分开。

参考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
65
66
67
68
#include <cstdio> 
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int data[7];
int dp[60001];
int m;
void ZeroOnePack(int value,int weight)
{
	for(int v=m;v>=value;v--)
		dp[v]=max(dp[v],dp[v-value]+weight);
}
void CompletePack(int value,int weight)
{
	for(int v=value;v<=m;v++)
		dp[v]=max(dp[v],dp[v-value]+weight);
}
void MultiPack(int value,int weight,int amount)
{
	if(value*amount>=m)
	{
		CompletePack(value,weight);
		return;
	}
	for(int k=1;k<amount;k*=2)
	{
		ZeroOnePack(k*value,k*weight);
		amount-=k;
	}
	ZeroOnePack(amount*value,amount*weight);
}
int main()
{
	int count=1;
	while(1)
	{
		int sum=0;
		bool mark=true;
		for(int i=1;i<=6;i++)
		{
			cin>>data[i];
			sum+=data[i]*i;
			if(data[i])
				mark=false;
		}
		if(mark)
			break;
		cout<<"Collection #"<<count++<<":"<<endl;
		if(sum&1)
		{
			cout<<"Can't be divided."<<endl;
			cout<<endl;
			continue;
		}
		m=sum>>1;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=6;i++)
			if(data[i])
				MultiPack(i,i,data[i]);
		if(dp[m]==m)
			cout<<"Can be divided."<<endl;
		else
			cout<<"Can't be divided."<<endl;
		cout<<endl;
	}
	return 0;
}

思路

只要能把钻石总价值的一半放进背包中，就满足题意。首先求出sum，并sum的一半赋给m作为背包最大容量。接着6个位置中每个位置进行判断，若不为0则进入模版进
行判断。01背包和完全背包军用了一维数组形式的状态转移方程，注意01背包中循环是逆序，完全背包是正序即可。多重背包中，如果总价值大于背包的最大容量，那
么就可以等效为完全背包问题。否则进行二进制优化，优化的结果均带入01背包进行计算，最后得出的dp[m]与m进行判断。

注意事项

若总价值为奇数则可以直接剪枝，用sum&1的二进制方法比sum%2的方法更简洁。sum&1为0说明是偶数，为1说明是奇数。同样m=sum/2也可以用sum>>=1来表示，把
二进制数像右移动一位相当于缩小了2^1倍。

本文标题:DP问题专题一(Dynamic Programming) 背包入门

文章作者:Hippopmonkey

发布时间:2016-08-30, 21:33:28

最后更新:2016-08-31, 00:00:10

原始链接:http://xuboming8.github.io/2016/08/30/DP问题专题一-Dynamic-Programming-背包入门/

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

文章目录
  1. 1. 经典DP 背包问题
    1. 1.1. 三种基本背包问题的概念
    2. 1.2. 01背包
    3. 1.3. 完全背包
    4. 1.4. 多重背包
    5. 1.5. 二进制优化
      1. 1.5.1. 二维划为一维数组的正逆序问题
    6. 1.6. ACM-HDOJ 2546(01背包)
      1. 1.6.1. 参考AC代码
      2. 1.6.2. 思路
      3. 1.6.3. 注意事项
    7. 1.7. ACM-HDOJ 1963(完全背包)
      1. 1.7.1. 参考AC代码
      2. 1.7.2. 思路
      3. 1.7.3. 注意事项
    8. 1.8. ACM-HDOJ 1059(多重背包)
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
      4. 1.8.4. 注意事项
|