问题

题目描述

你有一架天平和 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

队列同理，将计算出的重量存入队列，每次选择一个砝码与队列最前面的数据计算和与差，然后弹出此队列最前面的数据，直到队列为空，进行下一次循环

解法一：回溯

具体分析

  1. 每个数据有三种状态——跳过、减去、加上。（函数传参需要choice来决定数据的处理）
  2. 数据处理后传递给下一次选择。（函数传参需要temp来记录每次处理数据后的值）
  3. 数据储存来记录是否已经得出过该结果。（set来存放计算的temp）
  4. 结果需要所有的组合数，全局变量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顺序结构

具体分析

  1. 使用set数组不会存相同的数据特性（遇见相同的会跳过）
  2. 每次选择一个砝码W，计算W与所有的set数组的组合并存入set。但是会有一个问题，set数组会一直变大，循环将无法结束。
  3. 引入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;
}

解法三：队列

具体分析

  1. 每次选择一个砝码与队列所有数据加减，检查是否已经存有其结果（无就存入队列并且counter++，有就跳过）。
  2. 同样会遇到解法二问题，队列将会变长，浪费时间，引入temp队列，将数据存入temp，一次循环结束将temp复制给queue。
  3. 每次选择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;
}