c語(yǔ)言復(fù)賽題-預(yù)覽頁(yè)
【正文】 行有2 個(gè)非負(fù)整數(shù) v p （其中v 表示該物品的價(jià)格（v≤10000），p 表示該物品的重要度（15）） 【輸出文件】 只有一個(gè)正整數(shù)，為不超過(guò)總錢(qián)數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（100000000） 【輸入樣例】 1000 5 800 2 400 5 300 5 400 3 200 2 【輸出樣例】 3900 背包問(wèn)題的解決辦法有很多，但是都不太容易理解，本算法采用窮舉法結(jié)合二進(jìn)制數(shù)據(jù)的排列來(lái)窮舉所有價(jià)值組合 主要思想： 根據(jù)物品的個(gè)數(shù)先計(jì)算出所有物品排列組合的排列數(shù)，每件物品取為1，不取為0 假設(shè)用n個(gè)物品，從n個(gè)物品中任意取出若干個(gè)的最大組合次數(shù)為：2^n1種，因此只要窮舉出2^n1種組合情況，計(jì)算出其中的最大價(jià)值組合，就是本題的算法 本題的關(guān)鍵是計(jì)算出對(duì)應(yīng)的二進(jìn)制數(shù)據(jù)列，每一種組合對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)列，然后根據(jù)二進(jìn)制數(shù)組的0，1值來(lái)形成物品不同的組合，從而計(jì)算出當(dāng)前二進(jìn)制組合下的價(jià)值和，通過(guò)2^n1比較后就能計(jì)算出最大價(jià)值 include int main() { int N,m。 //用于存放每件物品的重要度 int i,j,n,num。 fscanf(fp1,%d%d,amp。im。 //讀取數(shù)據(jù)：將各個(gè)物品的價(jià)格和重要度分別存放到對(duì)應(yīng)的數(shù)組當(dāng)中 } n=m。 //求得k的值，即為n種物品取舍的（0，1）組合總數(shù) 2^n1 n=m?！ ? /*****以下這段代碼段完成將num轉(zhuǎn)換成n位二進(jìn)制數(shù)組的過(guò)程*****/ while(num!=0) //其中第一個(gè)while循環(huán)完成了有效數(shù)值的轉(zhuǎn)換 { y=num%2?！ ?} while(n=0) //第二個(gè)while 循環(huán)用于將二進(jìn)制序列的高位置0 { bi[n]=0。jn?！ ?} //循環(huán)結(jié)束后，可求得本次組合的總價(jià)格Totalweight和總價(jià)值和ValueSum if(TotalWeightN) //首先考察計(jì)算出來(lái)的總價(jià)格是否超過(guò)了允許的總價(jià)格 { TotalWeight=0?！ ?TotalWeight=0。 //輸出最大的價(jià)值和的結(jié)果 fclose(fp1)。M和K由輸入文件提供，要求在輸出文件中打印出最后剩下的猴子的編號(hào)。稱(chēng)之為約瑟夫問(wèn)題。我們可以假設(shè)猴子就位的狀態(tài)用1表示，把猴子離開(kāi)的狀態(tài)用0表示。想法很簡(jiǎn)單，現(xiàn)在關(guān)鍵的問(wèn)題是如何解決當(dāng)報(bào)數(shù)到第M個(gè)猴子的時(shí)候如何使得下一個(gè)報(bào)數(shù)重新回到第1個(gè)猴子處，也就是如何使用一維數(shù)組來(lái)解決環(huán)型問(wèn)題的求解技巧。那么如何實(shí)現(xiàn)呢？解決環(huán)型數(shù)組循環(huán)遍歷元素的方法：對(duì)于環(huán)型數(shù)組移動(dòng)下標(biāo)時(shí)，我們?nèi)绻看卧趐++之后再加上p=p%M的話(huà)就能解決先前遇到的越界的問(wèn)題。 //指向當(dāng)前數(shù)組元素的下標(biāo) int NumOfKing?！ p1=fopen(,r)。 //從文件中讀取已知數(shù)據(jù) n=M。 //初試話(huà)狀態(tài)數(shù)組，所有猴子都是就位的 while(n1) //n當(dāng)前圈內(nèi)還剩下的猴子數(shù),控制循環(huán)在圈內(nèi)只剩下一只猴子時(shí)結(jié)束循環(huán) { while(n1 { if(a[p]==1 ) //如果當(dāng)前位置有猴子 { n1++。 //這一步是為了解決循環(huán)數(shù)組成環(huán)遍歷的目的 } n1=0?！ ?break?！ ?fclose(fp2)?！ ?void sort(int x,int y) { int i,j,k,t。t=x。 if(ij) {a[t]=a[j]。(k=a[i])) i++。 a[t]=k?！ ? } int main() {int i,j,k,m,n,head,tail,ans。i=n。i=n?！ ?sort(1,n)。in。 ans+=b[tail]。} else j+=2?！ ?}/n。amp。i++)/N。i++)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1