L3-001. 凑零钱-PAT团体程序设计天梯赛GPLT(01背包,动态规划)

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。

输入格式:

输入第一行给出两个正整数:N(<=104)是硬币的总个数,M(<=102)是韩梅梅要付的款额。第二行给出N枚硬币的正整数面值。数字间以空格分隔。

输出格式:

在一行中输出硬币的面值 V1 <= V2 <= … <= Vk,满足条件 V1 + V2 + … + Vk = M。数字间以1个空格分隔,行首尾不得有多余空格。若解不唯一,则输出最小序列。若无解,则输出“No Solution”。

注:我们说序列{A[1], A[2], …}比{B[1], B[2], …}“小”,是指存在 k >= 1 使得 A[i]=B[i] 对所有 i < k 成立,并且 A[k] < B[k]。

输入样例1:
8 9
5 9 8 7 2 3 4 1
输出样例1:
1 3 5
输入样例2:
4 8
7 2 4 3
输出样例2:
No Solution

分析:01背包问题,因为要输出从小到大的排列,可以先把硬币面额从大到小排列,然后用bool类型的choice[i][j]数组dp[i][j]是否选取,如果选取了就令choice为true;然后进行01背包问题求解,如果最后求解的结果不是恰好等于所需要的价值的,就输出No Soultion,否则从choice[i][j]判断选取的情况,i从n到1表示从后往前看第i个物品的选取情况,j从m到0表示从容量m到0是否选取(j = j – w[i]),把选取情况压入arr数组中,最后输出arr数组

 

【算法】动态规划笔记

  • 将一个复杂的问题分解成若干个子问题,通过综合子问题的最优解来得到原问题的最优解
  • 动态规划会将每个求解过的子问题的解记录下来,这样下一次碰到同样的子问题时,就可以直接使用之前记录的结果,而不是重复计算
  • 可以用递归或者递推的写法实现,递归的写法又叫记忆化搜索
  • 重叠子问题:如果一个问题可以被分解成若干个子问题,且这些子问题会重复出现,就称这个问题拥有重叠子问题。 一个问题必须拥有重叠子问题,才能用动态规划去解决。
  • 最优子结构:如果一个问题的最优解可以由其子问题的最优解有效地构造出来,那么称为这个问题拥有的最优子结构。最优子结构保证了动态规划中的原问题的最优解可以由子问题的最优解推导而来
  • 动态规划与分治的区别:都是分解为子问题然后合并子问题得到解,但是分治分解出的子问题是不重叠的
  • 动态规划与贪心的区别:都有最优子结构,但是贪心直接选择一个子问题去求解,会抛弃一些子问题,这种选择的正确性需要用归纳法证明,而动态规划会考虑所有的子问题

动态规划的递归和递推写法

  • 递归写法

  • 递推写法

最大连续子序列和

  • 给定序列,求连续的子序列要求和最大,求最大的和为多少
  • dp[i]表示以a[i]作为末尾的连续序列的最大和(a[i]必须是末尾被选的数啊啊),dp数组中所有的数据的最大值就是所求
  • 因为a[i]一定是所选序列的末尾,所以分为两种情况:
    • a[i]开始,a[i]结束
    • 某数开始,到a[i]结束(最大和是dp[i-1] + a[i])
  • 所以递推方程为dp[i] = max(a[i], dp[i-1]+a[i])

最长不下降子序列(LIS)

  • 求一个序列的最长的子序列(可以不连续),使得这个子序列是不下降的
  • dp[i]表示必须以a[i]结尾的最长不下降子序列的长度
  • dp[i] = max{1, dp[j] + 1}; // j从1 ~ i-1 且必须满足a[j] <= a[i]

最长公共子序列(LCS)

  • 给定两个字符串或者数字序列A和B,求一个字符串,使得这个字符串是A和B的最长公共部分(子序列可以不连续)
  • dp[i][j]表示A的第i位之前和B的第i位之前的这两个序列的LCS最长公共子序列的长度(下标从1开始)
  • 那么dp[lena][lenb]即为所求
  • 递推方程:
    • 当a[i] == b[j] : dp[i][j] = dp[i-1][j-1] + 1
    • 当a[i] != b[j] : dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    • 边界:dp[i][0] = dp[0][j] = 0(0 <= i <= n, 1 <= j <= m)

最长回文子串

  • 给出一个字符串s,求s的最长回文字串的长度
  • dp[i][j]表示s[i]到s[j]所表示的字串是否是回文字串。只有0和1
  • 递推方程:
    • 当s[i] == s[j] : dp[i][j] = dp[i+1][j-1]
    • 当s[i] != s[j] : dp[i][j] =0
    • 边界:dp[i][j] = 1, dp[i][i+1] = (s[i] == s[i+1]) ? 1 : 0
  • 因为i、j如果从小到大的顺序来枚举的话,无法保证更新dp[i][j]的时候dp[i+1][j-1]已经被计算过。因此不妨考虑按照字串的长度和子串的初试位置进行枚举,即第一遍将长度为3的子串的dp的值全部求出,第二遍通过第一遍结果计算出长度为4的子串的dp的值…这样就可以避免状态无法转移的问题

DAG最长路

背包问题

  • 多阶段动态规划问题:有一类动态规划可解的问题,它可以描述成若干个有序的阶段,且每个阶段的状态有关,一般把这类问题称为多阶段动态规划问题

01背包问题

  • 有n件物品,每件物品的重量为w[i],价值为c[i]。现有一个重量为V的背包,问如何选取物品放入背包,使得背包内物品的总价值最大。其中每种物品只有1件
  • dp[i][j]表示前i件物品恰好装入容量为j的背包所能获得的最大价值
    • 不放第i件物品,则dp[i][j] = dp[i-1][j]
    • 放第i件物品,那么问题转化为前i – 1件物品恰好装入容量j – w[i]的背包中所能获得的最大价值dp[i-1][j-w[i]] + c[i]
  • 递推方程dp[i][j] = max{ dp[i-1][j], dp[i-1][j-w[i]]+c[i] }

  • 一维:

完全背包问题

  • 有n种物品,每种物品的单件重量为w[i],价值为c[i]。现有一个容量为v的背包,问如何选取物品放入背包,使得背包内物品的总价值最大。其中每种物品有无穷件
  • 递推方程:dp[i][j] = max(dp[i-1][v], dp[i][j-w[i]] + c[i])
  • 和01背包不同,这里的j的枚举顺序为正向枚举,而且是dp[i][j-w[i]]

1068. Find More Coins (30)-PAT甲级真题(01背包)

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the face values V1 <= V2 <= … <= Vk such that V1 + V2 + … + Vk = M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead.

Note: sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].

Sample Input 1:
8 9
5 9 8 7 2 3 4 1
Sample Output 1:
1 3 5
Sample Input 2:
4 8
7 2 4 3
Sample Output 2:
No Solution
题目大意:用n个硬币买价值为m的东西,输出使用方案,使得正好几个硬币加起来价值为m。从小到大排列,输出最小的那个排列方案
分析:01背包问题,因为要输出从小到大的排列,可以先把硬币面额从大到小排列,然后用bool类型的choice[i][j]数组dp[i][j]是否选取,如果选取了就令choice为true;然后进行01背包问题求解,如果最后求解的结果不是恰好等于所需要的价值的,就输出No Soultion,否则从choice[i][j]判断选取的情况,i从n到1表示从后往前看第i个物品的选取情况,j从m到0表示从容量m到0是否选取(j = j – w[i]),把选取情况压入arr数组中,最后输出arr数组

 

蓝桥杯 ADV-205 算法提高 拿糖果(动态规划)

问题描述
妈妈给小B买了N块糖!但是她不允许小B直接吃掉。
  假设当前有M块糖,小B每次可以拿P块糖,其中P是M的一个不大于根号下M的质因数。这时,妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
  现在小B希望知道最多可以拿多少糖。
输入格式
  一个整数N
输出格式
  最多可以拿多少糖
样例输入
15
样例输出
6
数据规模和约定
N <= 100000

分析:动态规划问题~~首先呢~创建一个满足不大于根号下最大值MAXN的素数表,然后对素数表里面的数逐个遍历~
构建一个dp[i]数组,表示当糖果数量为i的时候所能拿的最多的糖果数量~
对于dp[i]的值:因为小B只能每次拿不大于根号下i的质因数,遍历素数表中满足条件的素数(prime[j] <= sqrt(i) && i % prime[j] == 0),更新dp[i]的值为(dp[i-2*prime[j]] + prime[j])的最大值~
即:dp[i] = max(dp[i], dp[i-2*prime[j]] + prime[j]);