1151&nbsp;&nbsp;&nbsp;&nbsp;解&nbsp;&nbsp;題&nbsp;&nbsp;報&nbsp;&nbsp;告<br>														韓霖<br>	這道題說的是給你一個Piggy&nbsp;Bank可以往里面放硬幣。然后告訴你它裝硬幣前和裝硬幣后的<br>質量E,&nbsp;F，以及硬幣的種類N，每種硬幣的質量W和面值P。然后求Piggy&nbsp;Bank在給定的E，F條<br>件下最少能裝多少面額的硬幣。<br>	這是一道動規的題，很像。我的具體做法是先用一個整型變量iWheight&nbsp;=&nbsp;F&nbsp;–&nbsp;E，表示硬幣<br>的總質量，然后開一個數組Wheight[&nbsp;100001&nbsp;]，Wheight[&nbsp;n&nbsp;]&nbsp;表示當硬幣質量為n時的最少<br>面額。給Wheight的第零個元素賦值為0，其它元素賦值為-1，表示當前找不到滿足條件的硬幣<br>組合。用一個iCoin[&nbsp;5000&nbsp;][&nbsp;2&nbsp;]存放硬幣的信息，iCoin[&nbsp;n&nbsp;][&nbsp;0&nbsp;]表示第n種硬幣的面值，<br>iCoi[&nbsp;n&nbsp;][&nbsp;1&nbsp;]表示第n種硬幣的質量。然后可以知道Wheight[&nbsp;m&nbsp;]與前面元素的關系為Whei<br>ght[&nbsp;m&nbsp;]&nbsp;=&nbsp;Min(&nbsp;Wheight[&nbsp;m&nbsp;–&nbsp;iCoin[&nbsp;0,1……N&nbsp;][&nbsp;1&nbsp;]&nbsp;]&nbsp;+&nbsp;iCoin[&nbsp;0,1……N&nbsp;][&nbsp;0&nbsp;]&nbsp;)<br>&nbsp;。最后，如果Wheight[&nbsp;iWheight&nbsp;]&nbsp;==&nbsp;-1，則輸出&nbsp;”&nbsp;This&nbsp;is&nbsp;impossible.&nbsp;”，否則輸出<br>Wheight[&nbsp;iWheight&nbsp;]的值。源代碼如下：<br>#include&nbsp;&lt;stdio.h&gt;<br>int&nbsp;main()<br>{<br>	long&nbsp;int&nbsp;T,&nbsp;E,&nbsp;F,&nbsp;Weight[&nbsp;100001&nbsp;],&nbsp;P,&nbsp;W,&nbsp;n,&nbsp;m,&nbsp;iWeight,&nbsp;N,&nbsp;iCoin[&nbsp;5000&nbsp;][&nbsp;2&nbsp;],&nbsp;<br>a,&nbsp;iMin;<br>	scanf&nbsp;(&quot;%ld&quot;,&nbsp;&amp;T);<br>	for&nbsp;(n&nbsp;=&nbsp;0;&nbsp;n&nbsp;&lt;&nbsp;T;&nbsp;n++)<br>	{<br>		for&nbsp;(m&nbsp;=&nbsp;0;&nbsp;m&nbsp;&lt;=&nbsp;10000;&nbsp;m++)<br>			Weight[&nbsp;m&nbsp;]&nbsp;=&nbsp;-1;<br>		scanf&nbsp;(&quot;%ld%ld&quot;,&nbsp;&amp;E,&nbsp;&amp;F);<br>		iWeight&nbsp;=&nbsp;F&nbsp;-&nbsp;E;<br>		scanf&nbsp;(&quot;%ld&quot;,&nbsp;&amp;N);<br>		for&nbsp;(m&nbsp;=&nbsp;0;&nbsp;m&nbsp;&lt;&nbsp;N;&nbsp;m++)<br>			scanf&nbsp;(&quot;%d%d&quot;,&nbsp;&amp;iCoin[&nbsp;m&nbsp;][&nbsp;0&nbsp;],&nbsp;&amp;iCoin[&nbsp;m&nbsp;][&nbsp;1&nbsp;]);<br>		Weight[&nbsp;0&nbsp;]&nbsp;=&nbsp;0;<br>		for&nbsp;(m&nbsp;=1&nbsp;;&nbsp;m&nbsp;&lt;=&nbsp;iWeight;&nbsp;m++)<br>		{<br>			iMin&nbsp;=&nbsp;300000000;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;&nbsp;&nbsp;&nbsp;注意iMin的初值<br>			for&nbsp;(a&nbsp;=&nbsp;0;&nbsp;a&nbsp;&lt;&nbsp;N;&nbsp;a++)<br>			{<br>				if&nbsp;(m&nbsp;-&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;1&nbsp;]&nbsp;&gt;=&nbsp;0)<br>				{<br>					if&nbsp;(Weight[&nbsp;m&nbsp;-&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;1&nbsp;]&nbsp;]&nbsp;!=&nbsp;-1)<br>						if&nbsp;(iMin&nbsp;&gt;&nbsp;Weight[&nbsp;m&nbsp;-&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;1&nbsp;]&nbsp;]&nbsp;+&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;0&nbsp;])<br>							iMin&nbsp;=&nbsp;Weight[&nbsp;m&nbsp;-&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;1&nbsp;]&nbsp;]&nbsp;+&nbsp;iCoin[&nbsp;a&nbsp;][&nbsp;0&nbsp;];<br>				}<br>			}<br>			if&nbsp;(iMin&nbsp;!=&nbsp;300000000)<br>				Weight[&nbsp;m&nbsp;]&nbsp;=&nbsp;iMin;<br>		}<br>		if&nbsp;(Weight[&nbsp;iWeight&nbsp;]&nbsp;&gt;&nbsp;0)<br>			printf&nbsp;(&quot;The&nbsp;minimum&nbsp;amount&nbsp;of&nbsp;money&nbsp;in&nbsp;the&nbsp;piggy-bank&nbsp;is&nbsp;%d.\n&quot;,&nbsp;Weight[&nbsp;iWei<br>ght&nbsp;]);<br>		else<br>			printf&nbsp;(&quot;This&nbsp;is&nbsp;impossible.\n&quot;);<br>	}<br>	return&nbsp;0;<br>}<br>還有一點值得注意。請注意iMin的初值。我當時開始給iMin的初值為30000，因為我以前做類<br>似的題一直都用的30000。結果這道題測試數據過了，可提交上去老WA&nbsp;。后來才發現根據題中<br>E,&nbsp;F和W,&nbsp;P的取值范圍，硬幣的總面額是有可能大于30000的，30000不能大于Wheight[&nbsp;n&nbsp;]所<br>有的可能值，就會發生錯誤。后來，把iMin的初值改為300000000后，就AC了。這道題再一次<br>提醒了我，有時候經驗很重要，但不能完全憑經驗，還要根據具體的題意來做題，不能疏忽大<br>意。<br><font style='font-size:12pt'>
<br>
==============================================<br>
<a target=_blank href='http://vip.163.com' title='http://vip.163.com'><font color=green><b>安全穩定大容量，收費伊妹兒免費30日完美體驗~</b></a><br>
<a target=_blank href='http://mail.163.com' title='http://mail.163.com'><font color=red><b>中國最大的免費郵箱在等你 25兆空間 4兆附件！</b></a><br>
<a target=_blank href='http://popo.163.com' title='http://popo.163.com'><font color=green><b>點擊網易泡泡驚喜無限 全免費手機短信任你發!</b></a><br><br>