每日一题（砝码称重）

小白学视觉

发布于 2019-10-24 02:12:01

9710

文章被收录于专栏：深度学习和计算机视觉深度学习和计算机视觉

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）

特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。

砝码称重

问题描述

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），要求：计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。

输入数据

输入一行数据，包括六个正整数a1，a2，a3，a4，a5，a6，表示1g砝码有a1个，2g砝码有a2个，……，20g砝码有a6个。相邻两个整数之间用单个空格隔开。

输入样例

1 1 0 0 0 0

输出样例

分析

这道题我们可以利用穷尽的方法将砝码所有的组成情况都计算出来，然后去掉非重复的即可，但是这种办法十分的笨拙，而且在组成可测量的重量重复次数比较多的时候，就显得更加的没有必要了。另外，本题小白想使用C++里面比较好用的'set'关联容器。set关联容器可以自动的去重复和排序，是一个比较好的容器，感兴趣的小伙伴可以百度一下，同时也建议同时搜索一下map关联容器。

这道题，加入我们有一个1g砝码，我们只能称出1g，如果在给你一个2g砝码，我们能称出1g，2g，3g的重量。我们看一下这3种情况怎么来的，它是有原先的1g，与新加入的2g砝码自己称出的重量2g和1g+2g，去掉重复后组成的。那么此时如果在给一个1g砝码，可以称出的重量是，1g，2g，3g，4g：它是由原先的1g，2g，3g，与新加入的1g砝码自己称出的重量1g和1g+1g，1g+2g，1g+3g，去掉重复后组成的。利用这规律，n个砝码就可以看成是n-1个砝码后再重新给1个砝码的情况。因此利用set里面的自动去重复可以完成部分工作，我们只需要写出新给1个砝码后所增加的情况就可以了。

代码

#include <iostream>
#include <set>
#include <vector>
using namespace std;

class Solution
{
public:
  int sum;
  vector<int> everyweight;
  Solution();
  Solution(vector<int> &numweight, vector<int> &every) :everyweight(every), current({ 0 }), next({ 0 })
  {
      for (auto j = numweight.cbegin(),m=everyweight.cbegin(); j != numweight.cend(); j++,m++) //循环不同种类的砝码
      {
        for (int k = 1; k <= *j; k++)   //对输入的砝码个数进行循环
        {
          for (auto i = current.cbegin(); i !=current.cend(); i++)
          {
            next.insert(*i + (*m));    //向下一个set关联容器中存入能称出的重量
          }
          current = next;//更新关联容器
        }
      }
      sum = current.size()-1;
  }
private:
  set<int> current;
  set<int> next;
};

int main()
{
  vector<int> numweight;
  vector<int> every = { 1, 2, 3, 5, 10, 20 };
  int n;
  while (cin>>n)
  {
    numweight.push_back(n);
  }
  Solution solution(numweight,every);
  cout << solution.sum << endl;
  return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-08-01，如有侵权请联系 cloudcommunity@tencent.com 删除

容器

本文分享自小白学视觉微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

容器

登录后参与评论

0 条评论

热度