摘要： 問題描述： 有若干價(jià)值為分別為1，2 ，3，4，5，6的大理石，求總價(jià)值的均分策略。設(shè)價(jià)值為V的石頭重量為V,這批石頭的總價(jià)值為SUM,則問題轉(zhuǎn)化為選取若干大理石將容量為SUM/2的背包裝滿。 背包問題（參考“背包問題9講”） 有N件物品和一個(gè)容量為V的背包，第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。 f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值,則有： 0-1... 閱讀全文

摘要： 問題簡(jiǎn)述給出不同類型的一組郵票，類型面值可能相同。求符合總面值，且最多取4張郵票的最佳方案。最佳方案滿足以下要求：類型數(shù)最多。 如果類型數(shù)相同，則張數(shù)少者。 如果張數(shù)也相同，則單張面值最大者。 如果以上都相同，則無最佳方案（平局）。 問題分析搞了整整3天，絞盡腦汁也沒想出個(gè)好方案?？戳艘幌玛P(guān)于該題的discussion,許多人說這是個(gè)水題，直接暴搜就可以過?？墒窃趺炊枷氩幻靼兹绾伪┧选?最后在網(wǎng)上... 閱讀全文

摘要： 問題描述 人自出生起就有體力，情感和智力三個(gè)生理周期，分別為23，28和33天。一個(gè)周期內(nèi)有一天為峰值，在這一天，人在對(duì)應(yīng)的方面（體力，情感或智力）表現(xiàn)最好。通常這三個(gè)周期的峰值不會(huì)是同一天。現(xiàn)在給出三個(gè)日期，分別對(duì)應(yīng)于體力，情感，智力出現(xiàn)峰值的日期。然后再給出一個(gè)起始日期，要求從這一天開始，算出最少再過多少天后三個(gè)峰值同時(shí)出現(xiàn)。問題分析 首先我們要知道，任意兩個(gè)峰值之間一定相距整數(shù)倍的周期。假設(shè)... 閱讀全文

摘要： 最近沉迷于算法研究中，被POJ上ID為3700的這道題折磨了兩天后，終于順利通過了。深深震撼于程序性能因搜索方法的不同而產(chǎn)生的天壤之別。 該題描述如下：給出一組互不相同的整數(shù)，求可將其劃分為遞變（遞增或遞減）序列的最少個(gè)數(shù)。例如：給出5個(gè)數(shù)3，5，2，4，1，最少可將其劃分為2個(gè)序列。第一個(gè)序列為3，4，第二個(gè)序列為5，2，1。 我首先想到用多叉樹逐層計(jì)算。每個(gè)節(jié)點(diǎn)存放一個(gè)數(shù)組a, a中保存還未劃... 閱讀全文

摘要： 最近我們部門組織了一次編程競(jìng)賽。題目是這樣的：在三維空間中，給出一組射線和一組三角形，其中每條射線給出基點(diǎn)O和方向量D，每個(gè)三角形給出三個(gè)頂點(diǎn)A,B,C的坐標(biāo)，要求輸出這組射線和這組三角形的所有交點(diǎn)。出題者會(huì)給出數(shù)據(jù)量很大的輸入文件，可能包括幾萬條射線和幾萬個(gè)三角形，參加者提交自己的exe文件，在計(jì)算結(jié)果正確的前提下，運(yùn)行時(shí)間最少者獲勝。提交期限是一個(gè)星期。 其實(shí)這是光線跟蹤研究領(lǐng)域的基本問題，基... 閱讀全文