DP之背包基础

DP之背包基础
目录

DP简介

01背包问题

采药(01背包例题)

完全背包

疯狂的采药(完全背包例题)

背包变式

装箱问题

砝码称重

质数拆分

优化思考

DP简介

全称Dynamic Programming即动态规划

DP算法是解决多阶段决策过程最优化问题的一种常用方法。

多阶段决策过程是指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。

动态规划算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。

有时遇到暴搜宽搜TLE、贪心分治不理想的情况时，用动态规划常常能够起到出人意料的效果

01背包问题

01背包问题最经典的问题就是给一个背包，让你从中选取n个物品且每个物品只能选一次，求取在背包容量满足大于等于背包内物品总体积的情况下，所能装的物品的最大价值或者最小价值，在对于这种问题时，我们常常利用数学集合的思想来解决

我们将背包当中的物品体积开一个v[N]数组，价值开一个w[N]数组，最后开一个dp二维数组

v[N]一维数组来存储每个物品的体积，w[N]一维数组来存储每个物品的价值

dp[i][j]表示从i个物品当中选取，且体积不超过j的选法，因当第一种情况成立时，返回值为0，第二种情况成立时，选取物品放入，返回的是所选取物品的价值，所以dp二维数组的返回值是此种选法情况的背包中物品的最大价值

对应每个dp[i][j]可以分为两种选择情况：

第一种选择情况为从i - 1个物品当中选取，且总体积不超过j的情况

第二种选择情况为从i个物品当中选取，且总体积不超过j的情况

在对于dp二维数组的模拟过程之中我们发现第二种情况要用i来描述，第一种情况要用i - 1描述，二者不完全一致，因此为了优化，我们将第二种情况进行合理变式为从i - 1个物品当中选取，且总体积不超过j - v[i]的情况

因此dp二维数组在依次枚举的时候就可以这样做变动
```
f[i][j] = f[i - 1][j];//第一种情况
if(j >= v[i])f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i] + w[i]);//第二种情况
```
两种情况求取最大值，第二种情况的成立条件是第i件物品的体积小于背包体积

采药(01背包例题)

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？

题目描述

第一行有 2 个整数 T和M，用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目
接下来的 M行每行包括两个在1到 100之间（包括 1 和 100）的整数分别表示草药的时间和这株草药的价值。

输入

输出在规定的时间内可以采到的草药的最大总价值。

输出

输出在规定的时间内可以采到的草药的最大总价值

样例输入
```
70 3
71 100
69 1
1 2
```
样例输出
```
3
```
源代码

这道题目就是很经典的01背包问题，换汤不换药而已。背包中的物品换做了草药，背包的体积换作了最多能够使用的时间，物品的体积换做了采取草药的时间
```
#include <iostream>
using namespace std;
const int N = 3000+10;
int v[N];//存每株草药采取所花时间 
int w[N];//存每株草药的价值 
int T,M;
int dp[N][N];//存不同情况的不同最大价值 
int main()
{
	cin >> T >> M;
	for(int i = 1;i <= M;i ++ )cin >> v[i] >> w[i];
	for(int i = 1;i <= M;i ++ )
	{
		for(int j = 0;j <= T;j ++ )
		{
			dp[i][j] = dp[i - 1][j];
			if(j >= v[i])dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
		}
	}
	cout << dp[M][T];
	return 0;
}
```
优化后源代码
```
#include <iostream>
using namespace std;
const int N = 3000+10;
int v[N];//存每株草药采取所花时间 
int w[N];//存每株草药的价值 
int T,M;
int dp[N];//存不同情况的不同最大价值 
int main()
{
	cin >> T >> M;
	for(int i = 1;i <= M;i ++ )cin >> v[i] >> w[i];
	for(int i = 1;i <= M;i ++ )
	{
		for(int j = T;j >= v[i];j -- )
		{
			dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
		}
	}
	cout << dp[T];
	return 0;
}
```
完全背包

简单来说，就是01背包的变形，其本质与01背包相似，只是在完全背包当中，每一个物品可以被选择无数次，而不是只能够选择一次，一般来说，完全背包问题是要进行性优化的，否则会TLE

疯狂的采药(完全背包例题)

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题（采药）的不同点：

1. 每种草药可以无限制地疯狂采摘。

2. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入

输入第一行有两个整数，分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。

第2到第 (m+1) 行，每行两个整数，第 (i+1) 行的整数 ai, bi分别表示采摘第 i 种草药的时间和该草药的价值。

输出

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值

样例输入
```
70 3
71 100
69 1
1 2
```
样例输出
```
140
```
源代码(已优化)
```
#include <iostream>
using namespace std;
const int N = 1000000+10;
int v[N];//存每株草药采取所花时间 
int w[N];//存每株草药的价值 
int T,M;
int dp[N];//存不同情况的不同最大价值 
int main()
{
	cin >> T >> M;
	for(int i = 1;i <= M;i ++ )cin >> v[i] >> w[i];
	for(int i = 1;i <= M;i ++ )
	{
		for(int j = v[i];j <= T;j ++ )
		{
			dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
		}
	}
	cout << dp[T];
	return 0;
}
```
背包变式

装箱问题

题目描述

有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0<n≤30，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入

1个整数，表示箱子容量
1个整数，表示有m个物品
接下来n行，分别表示这n个物品的各自体积

输出

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

样例输入
```
24
6
8
3
12
7
9
7
```
样例输出
```
0
```
源代码

典型的完全背包问题，只不过求取最大值换做了求取最小值，简单变式即可
```
#include <iostream>
using namespace std;
const int N = 1000000+10;
int v[N];//存物品的体积 
int V,M;
int dp[N];//存不同情况的不同最大占用空间
int main()
{
	cin >> V >> M;
	for(int i = 1;i <= M;i ++ )cin >> v[i];
	for(int i = 1;i <= M;i ++ )
	{
		for(int j = v[i];j <= V;j ++ )
		{
			dp[j] = max(dp[j],dp[j - v[i]] + v[i]);
		}
	}
	cout << V - dp[V];
	return 0;
}
```
砝码称重

题目描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。
请你计算一共可以称出多少种不同的重量？
注意砝码可以放在天平两边。

输入

输入的第一行包含一个整数 N。
第二行包含 N 个整数：W1, W2, W3, · · · , WN。
对于 50% 的评测用例，1 ≤ N ≤ 15。
对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 100000。

输出

输出一个整数代表答案。

样例输入
```
3
1 4 6
```
样例输出
```
10
```
源代码

[样例说明]
能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。
1 = 1；
2 = 6 - 4(天平一边放 6，另一边放 4)；
3 = 4 - 1；
4 = 4；
5 = 6 - 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 - 1；
10 = 4 + 6；
11 = 1 + 4 + 6

此处的dp为状态01数组
```
#include <iostream>
using namespace std;
const int N = 3000+10;
int f[N][N];
int w[N];
int n,sum = 0,ans = 0;
//sum为累加砝码的最大值，即最大边界值
//无论砝码如何放置，每个砝码只能使用一次且最小值一定大于等于1 
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i ++ )//输入n个砝码的值 
	{
		cin >> w[i];
		sum += w[i];//累加最大边界值 
	}
	for(int i = 1;i <= n;i ++ )//外层循环砝码 
	{
		f[i][w[i]] = 1;//首先将该砝码重量标记为一种情况 
		for(int j = 1;j <= sum;j ++ )//内层循环砝码值 
		{
			if(f[i - 1][j] == 1)//若上层为1 
			{
				f[i][j] = 1;//则继承此种成立情况
				//对于新加的砝码值进行左右标记 
				f[i][j + w[i]] = 1; 
				f[i][abs(j - w[i])] = 1;
			}
		}
	}
	for(int i = 1;i <= sum;i ++ )//扫描1~最大边界值的砝码值 
	{
		if(f[n][i] == 1)ans ++ ;//若为1则证明此砝码值可以整出来 
	}
	cout << ans;
	return 0;
}
```
质数拆分

题目描述

2019可以被分解成若干个两两不同的素数，请问不同的分解方案有多少种？
注意：分解方案不考虑顺序，如 2 + 2017 = 2019 和 2017 + 2 = 2019 属于同一种方案。

输入

无

输出

55965365465060

样例输入

无

样例输出

55965365465060

源代码(已优化)

本题拉取素数优化的方法可以了解一下埃氏筛法与线性筛法
```
#include <iostream>
using namespace std;
const int N = 3000+10;
int prime[N];
bool isprime[N];
int idx = 0;
long long dp[N];
void init()//线性筛法拉取素数表 
{
	for(int i = 2;i <= 2019;i ++ )
	{
		if(!isprime[i])
		{
			prime[ ++ idx ] = i;
		}
		for(int j = 1;j <= idx && i <= 2019 / prime[j];j ++ )
		{
			isprime[i * prime[j]] = 1;
			if(i % prime[j] == 0)break;
		}
	}
}
int main()
{
	init();
	dp[0] = 1;//注意 
	for(int i = 1;i <= idx;i ++ )
	{
		for(int j = 2019;j >= prime[i];j -- )
		{
			dp[j] = dp[j] + dp[j - prime[i]];
		}
	}
	cout << dp[2019];
	return 0;
}
```
优化思考

二维数组的开辟范围当然是限制性很大的，所以利用dp二维数组并不能够用来表示当物品种类过大的情况，那么动态规划的算法也就有了鸡肋性，不过幸好，我们可以将一维数组优化为二维数组，优化的方式是将代码等价变形，并减少非必要的元素遍历

当我们将dp数组的首坐标删去之后，我们可以发现循环里面的
```
dp[i][j] = dp[i - 1][j];
```
变成了
```
dpj] = dp[j];
```
因此首行代码可以省去

根据第二行代码的情况进行减少数据遍历的优化，当第二行的情况成立时，j应该大于等于v[i]，也就是说在从0~v[i] - 1的情况都是无意义的遍历，因此的原本两种情况可以合并为一种情况
```
if(j >= v[i])dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
```
换做
```
dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
```
但是此时变形之后的一维数组相当于
```
dp[i][j] = max(dp[i - 1][j],dp[i][j - v[i]] + w[i]);
```
然而我们想要的是
```
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
```
所以我们要对于第二重循环的j进行改变
```
for(int i = 1;i <= M;i ++ )
{
	for(int j = 0;j <= T;j ++ )
	{
		dp[i][j] = dp[i - 1][j];
		if(j >= v[i])dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
	}
}
```
调整之后为
```
for(int i = 1;i <= M;i ++ )
{
	for(int j = T;j >= v[i];j -- )
	{
		dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
	}
}
```
谨记

第二重循环从大到小遍历之后的优化为01背包优化也就是
```
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
```
第二重循环从小到大的遍历为完全背包优化也就是
```
dp[i][j] = max(dp[i - 1][j],dp[i][j - v[i]] + w[i]);
```
相关阅读:
接口自动化用例设计总结
 基于javaweb的健身房管理系统(java+html+bootstrap+servlet+echarts+mysql)
冥想第五百九十四天
 vue-cli创建项目的步骤
 Windows安装SSH教程
 MySQL(进阶)--索引
 HashMap和ConcurrentHashMap区别
 13.求面积[有问题]
openGauss学习笔记-71 openGauss 数据库管理-创建和管理普通表-删除表中数据
 java 基于ssm+vue的公务员报名信息管理系统 elementui
原文地址：https://blog.csdn.net/couchpotatoshy/article/details/125583467

DP简介

01背包问题

采药(01背包例题)

完全背包

疯狂的采药(完全背包例题)

背包变式

装箱问题

砝码称重

质数拆分

优化思考