题解 | #称砝码#
太坑了，这题测试数据中有输入不规范的，需要处理输入时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);
}
}
}
查看13道真题和解析
