1036.html

<span style="font-family: Courier New;">แดงเตรียมตัวไปตั้งแค้มป์ในป่าเขาดงดิบกับเพื่อนๆ เขาไปเดินเลือกซื้ออุปกรณ์ที่ห้างสรรพสินค้าโชว์ห่วย ในร้านมีอุปกรณ์ตั้งแค้มป์ n ชิ้น ผลิตภัณฑ์ชิ้นที่ i มีราคา w<sub>i </sub>บาท<br />
<br />
แดงต้องการอุปกรณ์เหล่านี้ เพื่อใช้งานหลายอย่าง เช่น เหลาไม้ ขุดดิน ฟังเพลง เลื่อยไม้ กรองน้ำ ถลุงเหล็ก โม่แป้ง เป็นต้น รวมการใช้งานทั้งหมดมีได้ k แบบ<br />
<br />
แดงมีข้อมูลว่าอุปกรณ์แต่ละชิ้นทำอะไรได้บ้าง โดยสำหรับอุปกรณ์ที่ i และการใช้งานที่ j ค่า p(i,j) จะระบุว่า อุปกรณ์ดังกล่าวมีความสามารถใชงานสำหรับงานที่ j หรือไม่ กล่าวคือ p(i,j) = 1 เมื่ออุปกรณ์ที่ i สามารถทำงาน j ได้ และ p(i,j) = 0 เมื่ออุปกรณ์ชิ้นที่ i ทำไม่ได้<br />
<br />
ช่วยแดงเลือกเซตของอุปกรณ์ที่จะซื้อเพื่อให้สามารถใช้งานทำงานทุกงานได้ครบ กล่าวคือ สำหรับการใช้งาน j ใดๆ จะต้องมีอุปกรณ์ที่เลือกไปอย่างน้อย 1 อย่างที่สามารถใช้ทำงาน j ได้ นอกจากนี้ให้เลือกโดยใช้เงินน้อยที่สุดด้วย<br />
<br />
<u><strong>ข้อมูลป้อนเข้า</strong></u><br />
บรรทัดแรกมีจำนวนเต็ม n และ k (1 &lt;= n &lt;= 10 000; 1 &lt;= k &lt;= 8) จากนั้น ในบรรทัดที่ 1+i จะมีจำนวนเต็ม k+1 จำนวนเรียงตามลำดับดังนี้ wi p(i,1) p(i,2) . . . p(i,k)<br />
<br />
<u><strong>ข้อมูลส่งออก</strong></u><br />
มีหนึ่งบรรทัด เป็นจำนวนเงินที่น้อยที่สุดที่สามารถซื้อของที่ทำงานได้ครบทุกอย่าง<br />
<br />
<u><strong>ที่มา</strong></u><strong>: อ.ดร.จิตร์ทัศน์ ฝักเจริญผล</strong><br type="_moz" />
</span>
		<table>
			<tr>
				<th>ข้อมูลนำเข้า</th>
				<th>ข้อมูลส่งออก</th>
			</tr>	
		
			<tr>
				<td>5 3
<br />10 1 0 1
<br />30 0 1 1
<br />5 1 0 0
<br />4 0 0 1
<br />150 1 1 1
<br /></td>
				<td>35</td>
			</tr></table>