【正文】 7 8 value 1100 2250 3350 4500 5700 6800 7950 9050 item 3 2 3 ０ 1 3 2 3 由最后一個表格，可以得知在背包負(fù)重8公斤時，最多可以裝入9050元的水果，而最后一個裝入的 水果是3號，也就是草莓，裝入了草莓，背包只能再放入7公斤（81）的水果，所以必須看背包負(fù)重7公斤時的最佳解，最后一個放入的是2號，也就 是橘子，現(xiàn)在背包剩下負(fù)重量5公斤（72），所以看負(fù)重5公斤的最佳解，最后放入的是1號，也就是蘋果，此時背包負(fù)重量剩下0公斤（55），無法 再放入水果，所以求出最佳解為放入草莓、橘子與蘋果，而總價為9050元。實作 C include include define LIMIT 8 // 重量限制 define N 5 // 物品種類 define MIN 1 // 最小重量 struct body { char name[20]。 int size。 int price。 }。 typedef struct body object。 int main(void) { int item[LIMIT+1] = {0}。 int value[LIMIT+1] = {0}。 int newvalue, i, s, p。 object a[] = {{李子, 4, 4500}, {蘋果, 5, 5700}, {橘子, 2, 2250}, {草莓, 1, 1100}, {甜瓜, 6, 6700}}。 for(i = 0。 i N。 i++) { for(s = a[i].size。 s = LIMIT。 s++) { p = s a[i].size。 newvalue = value[p] + a[i].price。 if(newvalue value[s]) {// 找到階段最佳解 value[s] = newvalue。 item[s] = i。 } } } printf(物品\t價格\n)。 for(i = LIMIT。 i = MIN。 i = i a[item[i]].size) { printf(%s\t%d\n, a[item[i]].name, a[item[i]].price)。 } printf(合計\t%d\n, value[LIMIT])。 return 0。 } Java class Fruit { private String name。 private int size。 private int price。 public Fruit(String name, int size, int price) { = name。 = size。 = price。 } public String getName() { return name。 } public int getPrice() { return price。 } public int getSize() { return size。 }}public class Knapsack { public static void main(String[] args) { final int MAX = 8。 final int MIN = 1。 int[] item = new int[MAX+1]。 int[] value = new int[MAX+1]。 Fruit fruits[] = { new Fruit(李子, 4, 4500), new Fruit(蘋果, 5, 5700), new Fruit(橘子, 2, 2250), new Fruit(草莓, 1, 1100), new Fruit(甜瓜, 6, 6700)}。 for(int i = 0。 i 。 i++) { for(int s = fruits[i].getSize()。 s = MAX。 s++) { int p = s fruits[i].getSize()。 int newvalue = value[p] + fruits[i].getPrice()。 if(newvalue value[s]) {// 找到階段最佳解 value[s] = newvalue。 item[s] = i。 } } } (物品\t價格)。 for(int i = MAX。 i = MIN。 i = i fruits[item[i]].getSize()) { (fruits[item[i]].getName()+ \t + fruits[item[i]].getPrice())。 } (合計\t + value[MAX])。 }} Gossip: 蒙地卡羅法求 PI 說明蒙地卡羅為摩洛哥王國之首都，該國位于法國與義大利國境，以賭博聞名。蒙地卡羅的基本原理為以亂數(shù)配合面積公式來進(jìn)行解題，這種以機(jī)率來解題的方式帶有賭博的意味，雖然在精確度上有所疑慮，但其解題的思考方向卻是個值得學(xué)習(xí)的方式。解法蒙地卡羅的解法適用于與面積有關(guān)的題目，例如求PI值或橢圓面積，這邊介紹如何求PI值；假設(shè)有一個圓半徑為1，所以四分之一圓面積就為PI，而包括此四分之一圓的正方形面積就為1，如下圖所示： 如果隨意的在正方形中投射飛標(biāo)（點）好了，則這些飛標(biāo)（點）有些會落于四分之一圓內(nèi)，假設(shè)所投射的飛標(biāo)（點）有n點，在圓內(nèi)的飛標(biāo)（點）有c點，則依比例來算，就會得到上圖中最后的公式。至于如何判斷所產(chǎn)生的點落于圓內(nèi)，很簡單，令亂數(shù)產(chǎn)生X與Y兩個數(shù)值，如果X^2+Y^2等于1就是落在圓內(nèi)。 include include include define N 50000 int main(void) { int i, sum = 0。 double x, y。 srand(time(NULL))。 for(i = 1。 i N。 i++) { x = (double) rand() / RAND_MAX。 y = (double) rand() / RAND_MAX。 if((x * x + y * y) 1) sum++。 } printf(PI = %f\n, (double) 4 * sum / N)。 return 0。 }  Gossip: Eratosthenes篩選求質(zhì)數(shù) 說明除了自身之外，無法被其它整數(shù)整除的數(shù)稱之為質(zhì)數(shù)，要求質(zhì)數(shù)很簡單，但如何快速的求出質(zhì)數(shù)則一直是程式設(shè)計人員與數(shù)學(xué)家努力的課題，在這邊介紹一個著名的 Eratosthenes求質(zhì)數(shù)方法。解法首先知道這個問題可以使用回圈來求解，將一個指定的數(shù)除以所有小于它的數(shù)，若可以整除就不是質(zhì)數(shù)，然而如何減少回圈的檢查次數(shù)？如何求出小于N的所有質(zhì)數(shù)？首先假設(shè)要檢查的數(shù)是N好了，則事實上只要檢查至N的開根號就可以了，道理很簡單，假設(shè)A*B = N，如果A大于N的開根號，則事實上在小于A之前的檢查就可以先檢查到B這個數(shù)可以整除N。不過在程式中使用開根號會精確度的問題，所以可以使用 i*i = N進(jìn)行檢查，且執(zhí)行更快。再來假設(shè)有一個篩子存放1～N，例如：2　3　4　5　6　7　8　9　10　11　12　13　14　15　16　17　18　19　20　21 ........ N先將2的倍數(shù)篩去：2　3　5　7　9　11　13　15　17　19　21 ........ N再將3的倍數(shù)篩去：2　3　5　7　11　13　17　19　........ N再來將5的倍數(shù)篩去，再來將7的質(zhì)數(shù)篩去，再來將11的倍數(shù)篩去........，如此進(jìn)行到最后留下的數(shù)就都是質(zhì)數(shù)，這就是Eratosthenes篩選方法（Eratosthenes Sieve Method）。檢查的次數(shù)還可以再減少，事實上，只要檢查6n+1與6n+5就可以了，也就是直接跳過2與3的倍數(shù)，使得程式中的if的檢查動作可以減少。 實作 C include include define N 1000 int main(void) { int i, j。 int prime[N+1]。 for(i = 2。 i = N。 i++) prime[i] = 1。 for(i = 2。 i*i = N。 i++) { // 這邊可以改進(jìn) if(prime[i] == 1) { for(j = 2*i。 j = N。 j++) { if(j % i == 0) prime[j] = 0。 } } } for(i = 2。 i N。 i++) { if(prime[i] == 1) { printf(%4d , i)。 if(i % 16 == 0) printf(\n)。 } } printf(\n)。 return 0。 }  Gossip: 超長整數(shù)運(yùn)算（大數(shù)運(yùn)算）說明基于記憶體的有效運(yùn)用，程式語言中規(guī)定了各種不同的資料型態(tài)，也因此變數(shù)所可以表達(dá)的最大整數(shù)受到限制，例如123456789123456789這樣的 整數(shù)就不可能儲存在long變數(shù)中（例如C/C++等），我們稱這為long數(shù)，這邊翻為超長整數(shù)（避免與資料型態(tài)的長整數(shù)翻譯混淆），或俗稱大數(shù)運(yùn)算。解法一個變數(shù)無法表示超長整數(shù)，則就使用多個變數(shù)，當(dāng)然這使用陣列最為方便，假設(shè)程式語言的最大資料型態(tài)可以儲存至65535的數(shù)好了，為了計算方便及符合使用十進(jìn)位制的習(xí)慣，讓每一個陣列元素可以儲存四個位數(shù)，也就是0到9999的數(shù)，例如： 很多人問到如何計算像50!這樣的問題，解法就是使用程式中的乘法函式，至于要算到多大，就看需求了。由于使用陣列來儲存數(shù)值，關(guān)于數(shù)值在運(yùn)算時的加減乘除等各種運(yùn)算、位數(shù)的進(jìn)位或借位就必須自行定義，加、減、乘都是由低位數(shù)開始運(yùn)算，而除法則是由高位數(shù)開始運(yùn)算，這邊直接提供加減乘除運(yùn)算的函式供作參考，以下的N為陣列長度。 void add(int *a, int *b, int *c) { int i, carry = 0。 for(i = N 1。 i = 0。 i) { c[i] = a[i] + b[i] + carry。 if(c[i] 10000) carry = 0。 else { // 進(jìn)位 c[i] = c[i] 10000。 carry = 1。 } } } void sub(int *a, int *b, int *c) { int i, borrow = 0。 for(i = N 1。 i = 0。 i) { c[i] = a[i]