题解 | #称砝码#

太坑了，这题测试数据中有输入不规范的，需要处理输入时Trim()一下😂

处理输入后，按照每个重量的砝码的数量，把所有砝码塞到一个容器中，完成初步处理。

然后是重头戏：

1、求得所有组合方式并且去重。去重那就很自然想到用Dictionary或者和HashSet当做容器。由于需要记录的数据只有“某种组合方式的总重”这一个，所以选用HashSet<int>。

2、然后是求所有可能总重，核心算法如下：

HashSet<int> combinations = new Hashset<int> { 0 }; // 初始化先将选取0个砝码的情况计入

foreach weight in all_weights:

foreach combo in combinations:

combinations.Add(combo + weight )

return combinations.Count

每次向HashSet加入一个新的砝码的时候，都会将新砝码和已经尝试过的去重的组合组合起来，如果形成新组合，那么HashSet就会扩容；否则会被去重。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectSample
{
    //HJ41
    class Program
    {
        static void Main(string[] args)
        {
            int variation = int.Parse(Console.ReadLine());
            string wei_str = Console.ReadLine().Trim();
            int[] weights = wei_str.Split(' ')
                .Select(o => int.Parse(o)).ToArray();
            string cou_str = Console.ReadLine().Trim();
            int [] counts = cou_str.Split(' ')
                .Select(o => int.Parse(o)).ToArray();

            List<int> weights_with_rep = new List<int>();
            for (int i = 0; i < counts.Length; i++) 
            {
                var c = counts[i];

                for (int j = 0; j < c; j++) 
                {
                    weights_with_rep.Add(weights[i]);
                }
            }

            HashSet<int> tW= new HashSet<int> { 0 };
            for (int i = 0; i < weights_with_rep.Count; i++) 
            {
                foreach (var w in tW.ToList()) 
                {
                    tW.Add(w + weights_with_rep[i]);
                }
            }

            Console.WriteLine(tW.Count);
        }
    }
}