砝码称重
问题
题目描述
你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1, W2, · · · , WN。
请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数:W1, W2, W3, · · · , WN。
输出格式
输出一个整数代表答案。样例输入
3
1 4 6
样例输出
10
提示样例说明
能称出的 10 种重量是:1、2、3、4、5、6、7、9、10、11。
1 = 1;
2 = 6 4 (天平一边放 6,另一边放 4);
3 = 4 1;
4 = 4;
5 = 6 1;
6 = 6;
7 = 1 + 6;
9 = 4 + 6 1;
10 = 4 + 6;
11 = 1 + 4 + 6。评测用例规模与约定
对于 50% 的评测用例,1 ≤ N ≤ 15。
对于所有评测用例,1 ≤ N ≤ 100,N 个砝码总重不超过 100000。
题目分析
对于该问题,每个砝码都有三种选择,不放、放左边、放右边,如果以左边为基准,则放在左边相当于加上该砝码重量,右边减去。
可以使用回溯来对每一个砝码所有选择遍历
也可以使用简单的set,简单的双层for,一层按顺序遍历每次的砝码,内层计算选择的砝码与已经计算出的重量的和跟差,存入set
队列同理,将计算出的重量存入队列,每次选择一个砝码与队列最前面的数据计算和与差,然后弹出此队列最前面的数据,直到队列为空,进行下一次循环
解法一:回溯
具体分析
- 每个数据有三种状态——跳过、减去、加上。(函数传参需要choice来决定数据的处理)
- 数据处理后传递给下一次选择。(函数传参需要temp来记录每次处理数据后的值)
- 数据储存来记录是否已经得出过该结果。(set来存放计算的temp)
- 结果需要所有的组合数,全局变量counter
代码实现
int counterv = 0;//全局变量counter记录组合数
void WeightwithWeights1(vector<int>& nums, int i, unordered_set<int> &storage,int choice,int temp)
{
if (i == nums.size())
return;
if (choice == 0)
{
temp += nums[i];
if (!storage.count(abs(temp)))//为零加上该数据
{
counter++;
storage.insert(abs(temp));
}
for (int j = 0; j <= 2; j++)//进行下一选择
{
WeightwithWeights1(nums, i + 1, storage, j, temp);
}
}
if (choice == 1)
{
temp -= nums[i];
if (!storage.count(abs(temp)))//为一减去
{
counter++;
storage.insert(abs(temp));
}
for (int j = 0; j <= 2; j++)//进行下一次选择
{
WeightwithWeights1(nums, i + 1, storage, j, temp);
}
}
if (choice == 2)//为二跳过
{
for (int j = 0; j <= 2; j++)//进行下一选择
{
WeightwithWeights1(nums, i + 1, storage, j, temp);
}
}
}
解法二:set顺序结构
具体分析
- 使用set数组不会存相同的数据特性(遇见相同的会跳过)
- 每次选择一个砝码W,计算W与所有的set数组的组合并存入set。但是会有一个问题,set数组会一直变大,循环将无法结束。
- 引入temp数组,依然将组合存入set,但是每次计算前将set复制给temp数组一份,将砝码跟temp进行加减。
代码实现
int WeighwithWeights2(vector<int>& weights)
{
unordered_set<int> res;
res.insert(0);
for (int weight : weights)
{
vector<int> temp(res.begin(), res.end());//使用temp保存上一次res的状态
for (int i = 0; i < temp.size(); i++)
{
res.insert(weight + temp[i]);//存下上次res各位跟此weight的和
if (abs(weight - temp[i]) != 0) {
res.insert(abs(weight - temp[i]));//差
}
}
res.insert(weight);//存weight
}
return res.size() - 1;
}
解法三:队列
具体分析
- 每次选择一个砝码与队列所有数据加减,检查是否已经存有其结果(无就存入队列并且counter++,有就跳过)。
- 同样会遇到解法二问题,队列将会变长,浪费时间,引入temp队列,将数据存入temp,一次循环结束将temp复制给queue。
- 每次选择queue中最前面的数据,然后弹出,循环结束标志为queue为空。
代码实现
int count = 0; int WeighwithWeights3(vector<int>& weights) { queue<int> weightQueue; weightQueue.push(0);//初始化一个0,便于第一个元素的操作与后面的一致 int count = 0; for (int weight : weights) { queue<int> weightTemp;//定义队列 while (!weightQueue.empty()) { int temp = weightQueue.front();//将temp赋值为队列最前面的数 weightQueue.pop(); if (!Find(weightTemp, temp + weight)) { weightTemp.push(temp + weight);//没找到队列最前面数与weight的和 count++; } if (!Find(weightTemp, abs(temp - weight))) { weightTemp.push(abs(temp - weight));//没找到差 count++; } if (!Find(weightTemp, temp))//检查有没有temp { weightTemp.push(temp); } } weightQueue = weightTemp;//将temp队列复制给队列,如果没有临时队列,队列长度会一直变长,循环将不会结束 } return count ; } bool Find(const queue<int> weight, int num)//查找weight中是否有num的函数 { queue<int> temp; temp = weight;//不这样将会对weight队列改变 while (!temp.empty()) { if (temp.front() == num) { return true; } temp.pop(); } return false; }
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 BroMikey!
评论