两个动态规划的经典问题

时间:2022-11-13 11:07:35

硬币问题

问题描述:设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。

对任意钱数0≦m≦20001,设计一个用最少硬币找钱m的方法。

算法设计:对于给定的1≦n≦10,硬币面值数组T和可用使用的各种面值的硬币个数数组Coins,以及钱数m,0≦m≦20001,计算找钱m的最少硬币数。

我们再回想一下实现动态规划的前提:

  • 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
  • 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关;
  • 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)。

在做这道题之前,我们先来看一个样例:

问题描述

假设有 1 元,3 元,5 元的硬币若干(无限),现在需要凑出 11 元,问如何组合才能使硬币的数量最少?

问题分析

乍看之下,我们简单的运用一下心算就能解出需要 2 个 5 元和 1 个 1 元的解。当然这里只是列出了这个问题比较简单的情况。当硬币的币制或者种类变化,并且需要凑出的总价值变大时,就很难靠简单的计算得出结论了。贪心算法可以在一定的程度上得出较优解,但不是每次都能得出最优解。

这里运用动态规划的思路解决该问题。按照一般思路,我们先从最基本的情况来一步一步地推导。

我们先假设一个函数 d(i) 来表示需要凑出 i 的总价值需要的最少硬币数量。

1.当 i = 0 时,很显然我们可以知道 d(0) = 0。因为不要凑钱了嘛,当然也不需要任何硬币了。注意这是很重要的一步,其后所有的结果都从这一步延伸开来。
2.当 i = 1 时,因为我们有 1 元的硬币,所以直接在第 1 步的基础上,加上 1 个 1 元硬币,得出 d(1) = 1。
3.当 i = 2 时,因为我们并没有 2 元的硬币,所以只能拿 1 元的硬币来凑。在第 2 步的基础上,加上 1 个 1 元硬币,得出 d(2) = 2。
4.当 i = 3 时,我们可以在第 3 步的基础上加上 1 个 1 元硬币,得到 3 这个结果。但其实我们有 3 元硬币,所以这一步的最优结果不是建立在第 3 步的结果上得来的,而是应该建立在第 1 步上,加上 1 个 3 元硬币,得到 d(3) = 1。

...

接着就不再举例了,我们来分析一下。可以看出,除了第 1 步这个看似基本的公理外,

其他往后的结果都是建立在它之前得到的某一步的最优解上,加上 1 个硬币得到。

得出:d(i) = d(j) + 1

这里 j < i。通俗地讲,我们需要凑出 i 元,就在凑出 j 的结果上再加上某一个硬币就行了。

那这里我们加上的是哪个硬币呢。嗯,其实很简单,把每个硬币试一下就行了:

假设最后加上的是 1 元硬币,那 d(i) = d(j) + 1 = d(i - 1) + 1。
假设最后加上的是 3 元硬币,那 d(i) = d(j) + 1 = d(i - 3) + 1。
假设最后加上的是 5 元硬币,那 d(i) = d(j) + 1 = d(i - 5) + 1。

我们分别计算出 d(i - 1) + 1d(i - 3) + 1d(i - 5) + 1 的值,取其中的最小值,即为最优解,也就是 d(i)

最后公式:

两个动态规划的经典问题

int main() {
    int n, m, dp[20002];
    cin >> n;//输入硬币种类
    int value[n + 1], coins[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> value[i] >> coins[i];//分别输入面值与数量
    cin >> m;//最后找钱m
    for (int i = 1; i < 20002; i++)
        dp[i] = 1000000;//一维数组存储结果初定义
    dp[0] = 0;
    
    
    for (int i = 1; i <= n; i++)//面值种类
        for (int j = 1; j <= coins[i]; j++)//面值数量
            for (int k = m; k >= value[i]; k--)
                dp[k] = min(dp[k - value[i]] + 1, dp[k]);//核心(先找面值大的硬币,)

    
    cout << (dp[m] < 1000000 ? dp[m] : -1) << endl;//问题无解输出-1
    return 0;
}

背包问题

5个物体,重量分别为3,5,7,8,9,价值分别为4,6,7,9,10,背包容量为22,物体不能分割,求装入背包物体最大价值,写出求解过程。

//题目:
//求解下面的背包问题。有5个体积是3,5,7,8和9,价值为4,6,7,9和10的物品,背包的容量是22。
#include<iostream>
using namespace std;
#define NUM 5 //物体的个数
#define CAPCITY 22 //背包的容量
int main(){
	//初始化每个物体的体积以及价值,注意数组第一个元素是0
    int volume[CAPCITY+1]={0,3,5,7,8,9};
	int value[NUM+1]={0,4,6,7,9};
	//新建一个二维表用于存储每一步的结果
	int result[NUM+1][CAPCITY+1];
 
	//初始化二维结果表,这里的初始化是指记录每次选择(每一步)的最大价值,注意这里的选择不是穷举啊,算法的逻辑不清楚的话可以看
    //算法图解
	for(int i=0;i<=NUM;i++){result[i][0]=0;}
	for(int j=0;j<=CAPCITY;j++){result[0][j]=0;}
	for(int i=1;i<=NUM;i++){
		for(int j=1;j<=CAPCITY;j++){
			result[i][j]=result[i-1][j];
			if(volume[i]<=j){
				result[i][j]=max(result[i][j],result[i-1][j-volume[i]]+value[i]);
			}
		}
	}
    //将包含选择结果的表打印下来
	for(int k=0;k<=NUM;k++){
		for(int l=0;l<=CAPCITY;l++){
			cout<<result[k][l];
			if(result[k][l]>9)
				cout<<' ';
			else
				cout<<"  ";
		}
		cout<<endl;
	}
	cout<<"由上表可知,背包内可装下的物品的最大价值是:"<<result[NUM][CAPCITY]<<endl;
    system("pause");
	return 0;
}

两个动态规划的经典问题