自学内容网 自学内容网
自学内容网 > 正文

合理的饭票设计（dfs与dp）

🕗 发布于 2025-01-22 02:59 深度优先  算法  动态规划  

题目介绍：

以前大学食堂都使用餐票吃饭，每顿饭菜钱可以为1角，2角，...，最多为n角。如果规定每次吃饭最多只能使用k张餐票，是否可以设计m种不同面值的餐票，使得餐票从1开始可以连续覆盖的面值范围恰好为 1 - n（角）？满足上述条件的方案有多少？

假设 n 的值不超过500，饭菜钱单位为角。
例如，
m=3, k=2, n=8, 则，面值为：{1,3,4} 恰好覆盖 1,2,...,8，此时，1角只需要1张面值为1的即可，2角需要2张面值为1的，3角只需要1张面值为3的，4角只需要1张面值为4的，5角需要1张面值为1的再加上1张面值为4的，6角需要2张面值为3的，7角需要1张面值为3再加上1张面值为4的，8角需要2张面值为4的。即：只需要2张面值的饭票即可覆盖1-8的范围（注意：一定是连续覆盖）。除了这三种面值之外，再没有其他方案的面值。因此，这样的方案有1种。

注释：题目强调了恰好连续覆盖，既要满足恰好，又要满足连续，也即首次断开的地方正好是n+1的位置

关于输入

第1行输入正整数 P, 表示后面有 P行
后面的P行分别为 m,k，n,其间以空格间隔

关于输出

对应输出 P行，若不存在 m 种面值的饭票，则输出0，若有，则输出方案数

样例输入：

4
3 2 5
3 2 6
3 2 8
3 2 9

样例输出：

0
3
1
0

解题思路：共两个思路

一、将问题分块解决

  1. 对于每一个样例，先找出它的所有组合方式

  2. 对于每一种组合，再判断其是否符合题目要求

1.找出所有可能组合

采用dfs（deep first search：深度优先搜索）的方式

dfs简介： 其是一种用于遍历或搜索树或图的算法。（熟悉可跳过）

其基本思想是从图的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。如果图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到所有顶点都被访问为止。‌

DFS算法通常通过递归来实现。递归的过程对应着深度，而回溯的过程对应着回退。具体来说，DFS算法从一个起始节点开始，沿着一条路径尽可能深入地搜索，直到无法继续或达到目标，然后回溯并探索其他路径。

总而言之：探索加回溯

举例：全排列问题

/*给出一个数n，输出1~n的全排列，按字典序输出*/

//例: 输入 2

//例: 输出 1，2   2，1

对于这类问题，用一般的数学思维，我们会画树状图去解决

 dfs的思路其实就是画树状图的思路，只不过dfs是将一个分支绘制完毕后再绘制下一个分支

 向下的弯箭头表示探索，向上表示回溯，灰色细线表示整个执行过程

以下是代码实现：

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> a;//记录所有排列的结果
vector<int> b;//存放当前排列
int used[11] = { 0 };//标记是否被使用
void dfs(int cur, int n)//cur指当前层数
{
if (cur == n)
{
a.push_back(b);
for (int i = 0; i < n; i++)
cout << b[i] << " ";
cout << endl;
return;
}
//搜至最后一层进行操作并返回
for (int i = 1; i <= n; i++)
{
if (used[i] == 0)//未被使用
{
b.push_back(i);
used[i] = 1;
dfs(cur + 1, n);
//递归调用（探索）
b.pop_back();
used[i] = 0;
//回溯
}
}
return;
}
int main()
{
int n;
cin >> n;
dfs(0,n);
return 0;
}

 dfs的代码实现也是格式化的，只需确定搜索层数、末次操作即可写出代码

优化的话就是加上更多限制条件（即剪枝），使搜索情况数更少，降低复杂度

当然，通过画树状图的方式我们可以看到，dfs有先天性的缺陷，即无法搜索过深的层级，因为其复杂度将以指数的速度增长

回到正题，我们要用dfs的方式探索所有的组合情况，其思路与全排列大同小异，代码也几乎一致
vector<vector<int>> a;//记录所有排列
vector<int> b;//记录当前排列
void DFS_1(int m, int n, int k, int cur)
{
if (cur == m)
{
if (Is_cloud(n, k, m))//判断是否“恰好连续覆盖”
a.push_back(b);
return;
}
if (cur == 0)//首层只能为一
{
b.push_back(1);
DFS_1(m, n, k, cur + 1);
}
else
{
for (int i = 1; i < n; i++)
{
if (b[cur - 1] < i)//确保递增
{
b.push_back(i);
DFS_1(m, n, k, cur + 1);
b.pop_back();
}
}
}
return;
}

从排列变为组合，我采用了不同的剪枝方法，但思路未发生变化

2.判断是否符合要求

该“小”问题描述：已知m个数的组合，最多可以在其中挑选k个数，判断其能否恰好连续覆盖1~n之间的所有数

思考过程：可以进行问题转化：对于1~n中特定的x，我站在x级台阶上，共有m种下楼梯的方式，最多只能下k次，能否恰好下到第0级台阶

首先确定n+1不可以，接着再确定1~n均可以

这样将该问题转化为“下楼梯问题”，仍然用dfs进行处理（当然也可以不转化直接dfs，不过二者复杂度相差不大，而且转化后更易剪枝），代码如下：

int DFS_2(int step,int k, int m)//step表示剩余的级数
{
if (step < 0)
return 0;
if (step == 0)
return 1;
if (k == 0)
return 0;
int sum = 0;
for (int i = 0; i < m; i++)
{
sum += DFS_2(step - b[i], k - 1, m);
if (sum > 0)//剪枝，sum>0即表明可以被覆盖，没有进行下去的必要
return sum;
}
return sum;
}
bool Is_cloud(int n, int k, int m)//判断能否恰好覆盖
{
//n+1不可以被覆盖
int ans = DFS_2(n + 1,k, m);
if (ans > 0)
return false;
//1~n都需被覆盖
for (int i = 1; i <= n; i++)
{
ans= DFS_2(i, k, m);
if (ans == 0)
return false;
}
return true;
}

3.总结

该方法用了两层dfs嵌套，虽然思路清晰，但是无法或者说难以处理深度增加得较高时的情形，但在处理一般简单且对复杂度要求不高的情况时有较好效果

二、整体看问题

思路一的问题在于复杂度过高，遍历次数过多，为了改进这个问题，就有了思路二

其大致思路描述：把挑选出合适的组合作为一个整体的问题，使用dfs的方法进行搜索，而将恰好连续覆盖作为过程性的剪枝条件

过程性是区别于结果性：在思路一中，在遍历完后，我再进行判断，这毫无疑问是结果性的；而在思路二，我将采用过程性的剪枝策略：假设最多使用k张，在已知我m张中第一张是1角的情况下，可以连续覆盖1~k的所有，为保证连续，我一定从2~k+1之中选择我的第二张，假设选择了x角，我又会产生一个可以连续覆盖的范围，假设是1~y，那么我下一张将会从x~y+1之间选择，以此类推

以下是代码：

int dp[1001] = { 0 };//记录每个面值所需的最小餐票数量
vector<int> par_value;//记录当前选择的餐票面值
int m, k, n;
int ans = 0;
void dfs(int cur, int length)//cur表示搜索深度（不超过m），length表示覆盖范围
{
    if (length < 0)
        return;
    if (cur > m)//当前深度超过m，检查是否满足条件
    {
        if (length == n)
            ans++;
        return;
    }
    int* tmp = new int[1001];//创建临时数组存储dp的值
    for (int i = par_value[cur - 1] + 1; i <= length + 1; i++)
    {
        par_value.push_back(i);//探索
        int range = min(i * k, n + 1);//可能需要改变的范围
        int j = 0;
        for (j = i; j <= range; j++)
        {
            tmp[j] = dp[j];//存储以便恢复
            dp[j] = min(dp[j], dp[j - i] + 1);//更新dp数组
            //j-i再加上一张i即为j
        }
        if (dp[n + 1] > k)//n+1未被覆盖
        {
            for (j = i; j <= range + 1; j++)//range+1是为了考虑最后一张票
                //如果range == n+1，那么由于我的if判断，其不会被遍历到
            {
                if (dp[j] > k)//j未被覆盖
                {
                    dfs(cur + 1, j - 1);//递归
                    break;
                }
            }
        }
        for (j = i; j <= range; j++)
            dp[j] = tmp[j];//回溯
        par_value.pop_back();
    }
}
int main()
{
    int num;
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        cin >> m >> k >> n;
        ans = 0;
        // 初始化dp数组
        for (int i = 1; i <= n + 1; i++)
            dp[i] = 100000;
        for (int i = 0; i <= k; i++)
            dp[i] = i;//1~k可以被表示
        par_value.push_back(0);//第0张无意义
        par_value.push_back(1);//第一张面值为1
        dfs(2, k);//从第二张开始递归
        cout << ans << endl;
        par_value.clear();
    }
    return 0;
}

我采用了动态规划的方式，dp数组中存放了该面值所对应的最小张数，dp[i] > k表示未被覆盖到，要从其前一位开始进行下一层搜索

进一步优化可能会考虑将vector转化为全局数组，因为在数据量上升到较高水平后，vector各种操作会严重拖慢效率

三、代码效率对比

测试用例：

3
6 3 52
5 5 100
6 4 80

1.方法一

 2.方法二

 结果不出所料，dp取代dfs将代码运行效率大幅提升


原文地址：https://blog.csdn.net/2401_87573457/article/details/144250382

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2025