窮舉法-砝碼秤重

2020-08-01

梅齊里亞克的砝碼:
4個重量均不相同的砝碼，重量合計為40克，每個重量都是整數克，
可使用天平秤出1～40克等所有整數克的物品。求這4個砝碼各多少克?
放置在天平的方式沒有限制，可能為放左邊(與物品放同一邊)、放右邊(與物品放不同邊)、不使用

如果不考慮數學知識，用窮舉法來解
以p1、p2、p3、p4代表放置方式，可能的值為 { 1、0、-1 }；以w1、w2、w3、w4代表4個砝碼重量
如此可以列出計算方式 w1*p1 + w2*p2 + w3*p3 + w4*p4 == 物品重量
窮舉法列出:
4個砝碼的所有可能重量 (符合w1+w2+w3+w4==40且w1!=w2!=w3!=w4)
4個砝碼的所有放置方式 (每個砝碼有3種可能，因此共81種)
物品重量 (1～40)
再跑迴圈一一檢查直到找出符合條件的砝碼重量與放置方式

// 直接寫光是砝碼重量與放置方式就有好幾層的迴圈嵌套了
for(int w1 = 1; w1 <=40; w1++)
{
	for(int w2 = w1+1; w1+w2 <=40; w2++)
	{
		for(int w3 = w2+1; w1+w2+w3 <=40; w3++)
		{
			int w4 = 40-(w1+w2+w3);
			if (w4 > w3)
			{
				for(int p1 = -1; p1 <=1; p1++)
				{
					for(int p2 = -1; p2 <=1; p2++)
					{
						for(int p3 = -1; p3 <=1; p3++)
						{
							for(int p4 = -1; p4 <=1; p4++)
							{
								...
							}
						}
					}
				}
			}
		}
	}
}

是不是想到這張圖了XD

雖然情境上不太一樣，但是層層的嵌套還是一樣令人目眩
這時我考慮使用yield return，將砝碼重量與放置方式的組合由主程序中抽取出去
雖然在本質上還是for loop，至少在主程序上可能會好看一點
再用LinqPad看了下結果

看來應該是沒問題
接著就是主程序了，思路很簡單，就是一一檢查
也懶得寫回傳了，就直接用LinqPad Dump出來吧

void Main()
{
	// 所有可能的砝碼組合
	var weightsCombos = FindWeightsCombos();
	
	// 所有可能的砝碼放置方法
	var putMethods = GetAllPutMethods();

	foreach(var ws in weightsCombos)
	{
		// 固定砝碼重量，對重量1~40物品都試著找出一種放置方式
		// 為了等一下方便顯示說明文字，這邊先把物品重量+放置方式都存進Tuple中
		var wpms = Enumerable.Range(1, 40).Select(i => (w:i, pm:FindMatchPutMethod(ws, putMethods, i)));
		
		// 如果物品重量1~40都都存在一種放置方式
		if (wpms.All(x => x.pm != null))
			wpms.Select(p => DisplayPut(p.w, ws, p.pm)).Dump();
	}
}

public string DisplayPut(int wi, int[] weights, int[] put)
{
	// 顯示為說明文字
	Func<int, string> decodePut = i => i==-1 ? "放左邊" : (i==1 ? "放右邊" : "不使用");
	return $"秤{wi}：" + string.Join("，", weights.Zip(put, (_w,_p) => $"重量{_w}的砝碼{decodePut(_p)}"));
}

public int[] FindMatchPutMethod(int[] weights, IEnumerable<int []> putMethods, int targetWeight)
{
	// 在多個putMethods中找出第一個符合 w1*p1 + w2*p2 + w3*p3 + w4*p4 == targetWeight的 putMethod，找不到時回傳null
	// 這邊用Zip+Sum計算 w1*p1 + w2*p2 + w3*p3 + w4*p4，長度不為4的狀況也可以計算
	// 再使用FirstOrDefault特性，在沒有符合的狀況下回傳default(int[])，也就是回傳null
	return putMethods.FirstOrDefault(pm => weights.Zip(pm, (w, p) => w*p).Sum() == targetWeight);
}

public IEnumerable<int []> FindWeightsCombos()
{
	for(int w1 = 1; w1 <=40; w1++)
	{
		for(int w2 = w1+1; w1+w2 <=40; w2++)
		{
			for(int w3 = w2+1; w1+w2+w3 <=40; w3++)
			{
				int w4 = 40-(w1+w2+w3);
				if (w4 > w3)
				{
					yield return new int[] { w1, w2, w3, w4 };
				}
			}
		}
	}
}

public IEnumerable<int []> GetAllPutMethods()
{
	for(int p1 = -1; p1 <=1; p1++)
		for(int p2 = -1; p2 <=1; p2++)
			for(int p3 = -1; p3 <=1; p3++)
				for(int p4 = -1; p4 <=1; p4++)
					yield return new int[] { p1, p2, p3, p4 };
}

回首頁