动态规划常见问题

r囧r小猫 2022-06-15 04:22 272阅读 0赞

**1.找零问题**  
问题描述：目前人民币面值有1元、5元、10元、20元、50元、100元，假设现在需要给顾客找零n元，有多少种面值组合方式？

问题思路：设f\[n\]\[j\]表示使用前j种面值组合成n元的组合方式种类数（每种面值可能用到，也可能不用），第j种面值为v\[j\]，那么f\[n\]\[j\] = f\[n\]\[j - 1\] + f\[n - v\[j\]\]\[j\]，其中f\[n\]\[j - 1\]表示不用第j种面值组合成n元的组合方式种类数，而f\[n - v\[j\]\]\[j\]理解成，首先使用一张第j种面值，则剩余n-v\[j\]元，可以继续使用第j种组合也可以不用。特别的，有f\[0\]\[j\] = 1。

C++：

#include <iostream>
    using namespace std;
    int v[] = {
       1,5,10,20,50,100};
    int f(int n ,int j){
        if(n == 0)     return 1;
        if(n < 0 || j < 0)  return 0;
        return f(n ,j - 1) + f(n - v[j], j);
    }
    int main(){
        int n;
        cin >> n;
        cout << f(n,6 - 1) << endl;
        return 0;
    }

测试用例：  
输入  
100  
输出  
344

**2.钢条切割问题**  
问题描述：一家公司购买长钢条，将其切割成短钢条出售，切割本身没有成本，长度为i的短钢条的价格为Pi。那给定一段长度为n的钢条和一个价格表Pi,求钢条的切割方案使得收益Rn最大。如一个Pi如下：  
![这里写图片描述][SouthEast]  
求长度为n的钢条所有切割方法的最大收益？

问题思路：把长度为n的钢条看做n段长度为1的钢条，从钢条的最左端开始的相邻连接点开始，可以选择切割或者不切割，故总共的切割方案有2的n-1次方（这是在假设每一小段钢条不一样的情况下），实际总的切割方案数可以利用上述的找零思想。现在问题是所有切割方法的最大收益，假设长度为n的钢条的所有切割方案中最大收益为f\[n\]，则f\[n\] = max\{Pi\[n\] ,f\[1\] + f\[n - 1\],f\[2\] + f\[n - 2\],…\}。

C++：

#include <iostream>
    using namespace std;
    void max_cut(int f[],int Pi[],int n){
        for(int i = 1;i <= n; ++i ){
            int profit = Pi[i]; //初始化长度为i的钢条切割最大收益为不进行切割的价值
            for(int j = 1;j <= i/2; ++j){
                profit = profit > (f[j] + f[i - j]) ? profit : (f[j] + f[i - j]);
            }
            f[i] = profit;
        }
    }
    int main(){
        int n,k;
        cin >> n;
        int *Pi = new int[n + 1]();
        int *f = new int[n + 1](); //必须初始化为0
        for(k = 1;k <= n; ++k){
            cin >> Pi[k];
        }
        max_cut(f,Pi,n);
        cout << f[n] << endl;
        return 0;
    }

测试用例：  
输入  
10  
1 5 8 9 10 17 17 20 24 30  
输出  
30

**3.01背包问题**  
问题描述：一个背包体积为V，有n件物品，对每件物品i，其体积为c\[i\]，价值为w\[i\]，求背包能容纳的最大价值。

问题思路：假设f\[v\]\[i\]表示体积为v的书包使用前i种（可以用也可以不用）容纳的最大价值，则f\[v\]\[i\] = max\{f\[v\]\[i - 1\],f\[v - c\[i\]\]\[i - 1\] + w\[i\]\}。

C++:

#include <iostream>
    using namespace std;
    void package01(int f[],int c[],int w[],int n,int V){
        for(int i = 1:i <= n; ++i){
            for(int v = V;v >= c[i]; --v){
                f[v] = f[v] > (f[v - c[i]] + w[i]) ? f[v] : (f[v - c[i]] + w[i]);
            }
        }
    }
    int main(){
        int n,V,k;
        cin >> n >> V;
        int *f = new int[V + 1](); //必须初始化为0
        int *c = new int[n + 1]();
        int *w = new int[n + 1]();
        for(k = 1;k <= n; ++k){
            cin >> c[k];
        }
        for(k = 1;k <= n; ++k){
            cin >> w[k];
        }
        package01(f,c,w,n,V);
        cout << f[V] <<endl;
        return 0;
    }

测试用例：  
输入  
4 10  
2 3 5 6  
3 4 7 8  
输出  
14

问题描述：输入一个整型数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

int max_array(int A[],int n){
        int max = 0,temp = 0;
        for(int i = 0;i < n; ++i){
            if(temp <= 0)   temp = A[i];
            else    temp += A[i];
            if(temp > max)  max = temp; 
        }
    }

[SouthEast]: /images/20220615/b4956e5d112741969d9fe3d4ca2bff86.png