跳转至

C++ 使用递归、回溯、动态规划算法实现一题多解

１. 引言

为了让大家更好理解递归、回溯、动态规划三者算法之间有关系，本文罗列了几道题目，分别使用递归、回溯、动态规划解决。会发现三者之间同工异曲，都是一种搜索模式，递归是正向搜索且返回；回溯是搜索到尽头后你自己看着办、然后再继续；动态规划可以理解为反向搜索。

要有一定深度的理解，需要自己反复练习且揣摩其中的细节之分。

2. 打家劫舍

2.1 问题描述

一个专业的盗贼，计划偷打劫街的房屋。每间房内都藏有一定的现金，你可以进入每一间房子，影响偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被盗贼闯入，系统会自动报警。

现给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例1： 输入：[1,2,3,1]

输出：4

解释：偷窃 1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。偷窃到的最高金额=1+3=4。

示例2：

输入：[2,7,9,3,1]

输出：12

解释：偷窃 1 号房屋(金额 = 2)，偷 3 号房屋(金 = 9)，接着偷 5 号房屋(金额 =1)偷窃到的最高金额=2+9+1=12。

2.2 递归实现

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
using namespace std;
//房间数量
int n;
//房间的金额
int m[100]= {0};
int djjsDg(int idx) {
    if(idx>n)return 0;
//偷， 进入下下个房间
    int t= m[idx]+djjsDg(idx+2);
//不偷，可以直接进行相邻房间
    int nt=djjsDg(idx+1);
    return max(t,nt);
}

2.2 回溯实现

C++
 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
#include <iostream>
using namespace std;
//房间数量
int n;
//房间的金额
int m[100]= {0};
//结果
int maxVal=0;
/*
*  sum 每次偷的金额
*  idx 从第几间房间开始偷
*/
void djjsHs(int sum,int idx) {
    for( int i=0; i<=1; i++ ) {
        sum+= m[idx]*i;
        if(idx>=n) {
            //最后一家
            maxVal=max(maxVal,sum);
        } else {
            //下一家
            djjs(sum, i==0?idx+1:idx+2 );
        }
        sum-= m[idx]*i;
    }
}

2.3 动态规划

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
using namespace std;
//房间数量
int n;
//房间的金额
int m[100];
int dp[100]= {0};
//结果
int res=0;
int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>m[i];
    }
    for(int i=1; i<=n; i++) {
        dp[i]=max( dp[i-1],m[i]+dp[i-2] );
        res=max(res,dp[i]);
    }
    cout<<res;
    return 0;
}

3. 找零钱

3.1 问题描述

给你k种面值的硬币，面值分别为c1, c2 ... ck，每种硬币的数量无限，再给一个总金额amount，问最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。

比如说k = 3，面值分别为 1，2，5，总金额amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。

3.2 递归实现

C++
 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
#include <iostream>
using namespace std;
int coins[5]= {1,5,10,21,25};
int money=10; //完全背包
// 记忆搜索
int cache[100]= {0}; //索引号：表示金额  值：结果，最少的硬币数
int zl(int m) {
    int res=m;
//出口一的写法
    //if(m==0)return 0;
//出口二的写法
    for(int i=0; i<5; i++) {
        if( m==coins[i] )return 1;
    }
    if(cache[m]!=0) {
        res =cache[m];
    } else {
        //子问题有哪些（子节点有多少个）
        for(int i=0; i<5; i++) {
            if(coins[i]<=m ) {
                res=min(res, 1+zl(m-coins[i]) ) ;
            }
        }
        cache[m]=res;
    }
    return res;
}

3.3 回溯实现

C++
 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 <iostream>
using namespace std;
//选择
int coins[5]= {1,5,10,21,25};
int money=10;
//结果
int res[100]= {0};
int minLen=money;
int show() {
    int count=0;
    for(int i=1; i<=money; i++) {
        if(res[i]) {
            count++;
            cout<<res[i]<<"\t";
        }
    }
    cout<<endl;
    return count;
}
void zlhs(int idx,int m ) {
//多个选择
    for(int i=0; i<5; i++) {
        if( m>=coins[i] ) {
            //选择
            res[idx]= coins[i];
            if( m-coins[i]==0 ) {
                //显示结果
                int res= show();
                minLen=min(minLen,res);
            } else {
                //下一个流程
                zlhs(idx+1,m-coins[i]);
            }
            res[idx]=0;
        }
    }
}

3.4 动态规划实现

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char** argv) {
    int money=0;
    cout<<"请输入零钱数:"<<endl;
    cin>>money;
//硬币类型
    int coins[5]= {1,5,10,21,25};
//状态数组，零钱需要找回的硬币数
    vector<int> dp(money+1, money+1);
    dp[0]=0;
    for(int i=1; i<=money; i++) {
        for(int j=0; i>=coins[j]; j++) {
            //求最小值
            dp[i]=dp[i] < dp[ i-coins[j] ]+1 ? dp[i] : dp[ i-coins[j] ]+1;
        }
    }
    cout<<dp[money]<<"\t";
    return 0;
}

4. 0-1背包

4.1 问题描述

有一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在用这个背包装物品，最多能装的价值是多少？

题目中的物品不可以分割，要么装进包里，要么不装，不能切成两块装一半。

如输入如下数据：

Text Only
1
N = 3, W = 6``wt = [ 1,2,7 ]``val = [4,3,2 ]

可以选择前两件物品装进背包，总重量 3 小于W，可以获得最大的价值是 7。

4.2 递归实现

C++
 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
#include <iostream>
#include <cmath>
using namespace std;
struct Goods {
//重量
    int weight;
//价值
    int price;
//物品状态 1 已经使用，0 未使用
    int isUse;
};
//0  1 （不可分割，数量有限）
//所有物品              0        1      2        3       4
Goods allGoods[5]= { {20,60,false},{30,120,false},{10,50,false},{20,20,false},{40,100,false} };
//背包重量
int bagWeight = 100;
//物品总数量
int totalNumber = 5;
int bag(int i,int wei) {
    int totalPrice=0;
    if(i==totalNumber)return 0;
    if( allGoods[i].weight>wei  ) {
        //物理存储空间：就是不能放下
        totalPrice= bag(i+1,wei);
    } else {
        //能放下：出现选择 放还是不放，看收益多少
        totalPrice=max(bag(i+1,wei-allGoods[i].weight)+allGoods[i].price , bag(i+1,wei) );
    }
    return totalPrice;
}

4.3 回溯实现

C++
 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
#include <iostream>
#include <cmath>
using namespace std;
struct Goods {
//重量
    int weight;
//价值
    int price;
//物品状态 1 已经使用，0 未使用
    int isUse;
};
//0  1 （不可分割，数量有限）
//所有物品              0        1      2        3       4
Goods allGoods[5]= { {20,60,false},{30,120,false},{10,50,false},{20,20,false},{40,100,false} };
//背包重量
int bagWeight = 100;
//物品总数量
int totalNumber = 5;
void showBag() {
    for(int i=0; i<5; i++) {
        if(allGoods[i].isUse)
            cout<<allGoods[i].weight<<","<<allGoods[i].price<<"\t";
    }
    cout<<endl;
}
//最大价值
int maxPrice=0;
//总价值
int totalPrice=0;
//idx 物品编号
void bag_(int idx,int wei) {
//两种状态
    for( int i=0; i<=1; i++ ) { //0  不放，  1 放
        if(wei>=allGoods[idx].weight*i) {
            allGoods[idx].isUse=i;
            totalPrice+=allGoods[idx].price*i;
            if(idx==4) {
                if(totalPrice>maxPrice ) {
                    maxPrice=totalPrice;
                    showBag();
                    cout<<maxPrice<<endl;
                }
            } else {
                bag_(idx+1, wei-allGoods[idx].weight*i) ;
            }
            //回溯
            allGoods[idx].isUse=false;
            totalPrice-=allGoods[idx].price*i;
        }
    }
}

4.4 动态规划实现

C++
 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
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char** argv) {
//物品信息
    int goods[3][3]= { {1,4},{2,3} };
//背包容量
    int bagWeight=0;
    cout<<"请输入背包容量："<<endl;
    cin>>bagWeight;
//状态表
    int db[4][bagWeight+1]= {0};
    for(int i=0; i<4; i++) {
        for(int j=0; j<bagWeight+1; j++) {
            db[i][j]=0;
        }
    }
    for(int w=1; w<4; w++) {
        for(int wt=1; wt<=bagWeight; wt++) {
            if( goods[w-1][0]>wt ) {
                //如果背包不能装下物品，保留背包上一次的结果
                db[w][wt]=db[w-1][wt];
            } else {
                //能装下,计算本物品价值和剩余容量的最大价值
                int val=goods[w-1][1] + db[w-1][ wt- goods[w-1][0] ];
                //背包原来的价值
                int val_= db[w-1][wt];
                //计算最大值
                db[w][wt]=val>val_?val:val_;
            }
        }
    }
    for(int i=1; i<3; i++) {
        for(int j=1; j<=bagWeight; j++) {
            cout<<db[i][j]<<"\t";
        }
        cout<<endl;
    }
    return 0;
}
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用