华为机试HJ41：称砝码（深度优先遍历dfs-Depth First Search）-阿里云开发者社区

华为机试HJ41：称砝码（深度优先遍历dfs-Depth First Search）

2023-10-17 144

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 华为机试HJ41：称砝码（深度优先遍历dfs-Depth First Search）

题目描述：

现有一组砝码，重量互不相等，分别为m1,m2,m3…mn；

每种砝码对应的数量为x1,x2,x3...xn。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。

注：

称重重量包括0

输入描述：

输入包含多组测试数据。

对于每组测试数据：

第一行：n --- 砝码数(范围[1,10])

第二行：m1 m2 m3 ... mn --- 每个砝码的重量(范围[1,2000])

第三行：x1 x2 x3 .... xn --- 每个砝码的数量(范围[1,6])

输出描述：

利用给定的砝码可以称出的不同的重量数

示例：

输入：

1 2

2 1

输出：

解题思路：

因为不超过十个砝码，全局创建number还有a、b两个数组，number表示砝码数量，a存储不同砝码的重量，b存储不同砝码的数量；用自定义的Statistical函数统计能称重的重量，用到的容器是unordered_set，这是为了去重，不同的组合如果得到的重量一致，保留一次即可，用set也可以实现，但是较慢。

自定义函数的逻辑：用递归的方法进行深度优先遍历，初始deep为0，开始进入循环并递归，直到deep达到最大值时实现第一次返回，此时容器中只存储了0重量；再在最深的节点处继续遍历，即加上最后一个砝码的一倍重量，存储，加上两倍重量再存储，直到遍历完最后一个砝码的数量；然后倒退一个节点，令倒数第二个砝码的一倍重量遍历一次加上最后一个砝码的各倍重量，再令倒数第二个砝码的两倍重量遍历一次加上最后一个砝码的各倍重量，以此类推；直到达到最大重量，即所有砝码的数量乘各自重量的和，递归结束。此时的容器尺寸即能称重的重量数。

测试代码：

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int number;
int a[11];
int b[11];
void Statistical(int deep,int weight,unordered_set<int> &s)
{
    if(deep>=number)
    {
        return;
    }
    for(int i=0;i<=b[deep];++i)
    {
        weight+=a[deep]*i;
        s.insert(weight);
        Statistical(deep+1,weight,s);
        weight-=a[deep]*i;
    }
    return;
}
int main()
{
    while(cin>>number)
    {
        for(int i=0;i<number;++i)
        {
            cin>>a[i];
        }
        for(int i=0;i<number;++i)
        {
            cin>>b[i];
        }
        unordered_set<int> s;
        Statistical(0, 0, s);
        cout<<s.size()<<endl;
    }
    return 0;
}

文章标签：

存储

容器

华为机试HJ41：称砝码（深度优先遍历dfs-Depth First Search）

题目描述：

输入描述：

输出描述：

示例：

解题思路：

测试代码：

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

华为机试HJ41：称砝码（深度优先遍历dfs-Depth First Search）

题目描述：

输入描述：

输出描述：

示例：

解题思路：

测试代码：

热门文章

最新文章

相关电子书