KnapsackProblem

[Algorithm Gossip: 背包问题（Knapsack Problem）]

说明

假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物品，假设是水果好了，水果的编号、单价与重量如下所示： 0 李子 4KG NT$4500 1 苹果 5KG NT$5700 2 橘子 2KG NT$2250 3 草莓 1KG NT$1100 4 甜瓜 6KG NT$6700

解法

背包问题是关于最佳化的问题，要解最佳化问题可以使用“动态规划”（Dynamic programming），从空集合开始，每增加一个元素就先求出该阶段的最佳解，直到所有的元素加入至集合中，最后得到的就是最佳解。 以背包问题为例，我们使用两个阵列value与item，value表示目前的最佳解所得之总价，item表示最后一个放至背包的水果，假设有负重量 1～8的背包8个，并对每个背包求其最佳解。 逐步将水果放入背包中，并求该阶段的最佳解：

• 放入李子 背包负重 1 2 3 4 5 6 7 8 value ０ ０ ０ 4500 4500 4500 4500 9000 item － － － ０ ０ ０ ０ ０

• 放入苹果 背包负重 1 2 3 4 5 6 7 8 value ０ ０ ０ 4500 5700 5700 5700 9000 item － － － ０ 1 1 1 ０

• 放入橘子 背包负重 1 2 3 4 5 6 7 8 value ０ 2250 2250 4500 5700 6750 7950 9000 item － 2 2 ０ 1 2 2 ０

• 放入草莓 背包负重 1 2 3 4 5 6 7 8 value 1100 2250 3350 4500 5700 6800 7950 9050 item 3 2 3 ０ 1 3 2 3

• 放入甜瓜 背包负重 1 2 3 4 5 6 7 8 value 1100 2250 3350 4500 5700 6800 7950 9050 item 3 2 3 ０ 1 3 2 3 由最后一个表格，可以得知在背包负重8公斤时，最多可以装入9050元的水果，而最后一个装入的 水果是3号，也就是草莓，装入了草莓，背包只能再放入7公斤（8-1）的水果，所以必须看背包负重7公斤时的最佳解，最后一个放入的是2号，也就 是橘子，现在背包剩下负重量5公斤（7-2），所以看负重5公斤的最佳解，最后放入的是1号，也就是苹果，此时背包负重量剩下0公斤（5-5），无法 再放入水果，所以求出最佳解为放入草莓、橘子与苹果，而总价为9050元。

实作

• Java class Fruit { private String name; private int size; private int price; public Fruit(String name, int size, int price) { this.name = name; this.size = size; this.price = 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 < fruits.length; 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; } } } System.out.println("物品\t价格"); for(int i = MAX; i >= MIN; i = i - fruits[item[i]].getSize()) { System.out.println(fruits[item[i]].getName()+ "\t" + fruits[item[i]].getPrice()); } System.out.println("合计\t" + value[MAX]); } }

EratosthenesPrime

Algorithm Gossip: Eratosthenes筛选求质数

说明

除了自身之外，无法被其它整数整除的数称之为质数，要求质数很简单，但如何快速的求出质数则一直是程式设计人员与数学家努力的课题，在这边介绍一个著名的 Eratosthenes求质数方法。

解法

首先知道这个问题可以使用回圈来求解，将一个指定的数除以所有小于它的数，若可以整除就不是质数，然而如何减少回圈的检查次数？如何求出小于N的所有质数？ 首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设A/B = N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到B这个数可以整除N。不过在程式中使用开根号会精确度的问题，所以可以使用 i/i <= N进行检查，且执行更快。 再来假设有一个筛子存放1～N，例如： 2　3　4　5　6　7　8　9　10　11　12　13　14　15　16　17　18　19　20　21 ........ N 先将2的倍数筛去： 2　3　5　7　9　11　13　15　17　19　21 ........ N 再将3的倍数筛去： 2　3　5　7　11　13　17　19　........ N 再来将5的倍数筛去，再来将7的质数筛去，再来将11的倍数筛去........，如此进行到最后留下的数就都是质数，这就是Eratosthenes筛选方法（Eratosthenes Sieve Method）。 检查的次数还可以再减少，事实上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍数，使得程式中的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++) { // 这边可以改进 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; }

• Java import java.util./; public class Prime { public static int[] findPrimes(final int max) { int[] prime = new int[max+1]; ArrayList list = new ArrayList(); for(int i = 2; i <= max; i++) prime[i] = 1; for(int i = 2; i/i <= max; i++) { // 这边可以改进 if(prime[i] == 1) { for(int j = 2/*i; j <= max; j++) { if(j % i == 0) prime[j] = 0; } } } for(int i = 2; i < max; i++) { if(prime[i] == 1) { list.add(new Integer(i)); } } int[] p = new int[list.size()]; Object[] objs = list.toArray(); for(int i = 0; i < p.length; i++) { p[i] = ((Integer) objs[i]).intValue(); } return p; } public static void main(String[] args) { int[] prime = Prime.findPrimes(1000); for(int i = 0; i < prime.length; i++) { System.out.print(prime[i] + " "); } System.out.println(); } }

SelectionInsertionBubble

Algorithm Gossip: 选择、插入、气泡排序

说明

选择排序（Selection sort）、插入排序（Insertion sort）与气泡排序（Bubble sort）这三个排序方式是初学排序所必须知道的三个基本排序方式，它们由于速度不快而不实用（平均与最快的时间复杂度都是O(n2)），然而它们排序的方式确是值得观察与探讨的。

解法

• 选择排序 将要排序的对象分作两部份，一个是已排序的，一个是未排序的，从后端未排序部份选择一个最小值，并放入前端已排序部份的最后一个，例如： 排序前：70 80 31 37 10 1 48 60 33 80

1. [1] 80 31 37 10 70 48 60 33 80 选出最小值1
2. [1 10] 31 37 80 70 48 60 33 80 选出最小值10
3. [1 10 31] 37 80 70 48 60 33 80 选出最小值31
4. [1 10 31 33] 80 70 48 60 37 80 ......
5. [1 10 31 33 37] 70 48 60 80 80 ......
6. [1 10 31 33 37 48] 70 60 80 80 ......
7. [1 10 31 33 37 48 60] 70 80 80 ......
8. [1 10 31 33 37 48 60 70] 80 80 ......
9. [1 10 31 33 37 48 60 70 80] 80 ......

• 插入排序 像是玩朴克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的适当位置，例如： 排序前：92 77 67 8 6 84 55 85 43 67

1. [77 92] 67 8 6 84 55 85 43 67 将77插入92前
2. [67 77 92] 8 6 84 55 85 43 67 将67插入77前
3. [8 67 77 92] 6 84 55 85 43 67 将8插入67前
4. [6 8 67 77 92] 84 55 85 43 67 将6插入8前
5. [6 8 67 77 84 92] 55 85 43 67 将84插入92前
6. [6 8 55 67 77 84 92] 85 43 67 将55插入67前
7. [6 8 55 67 77 84 85 92] 43 67 ......
8. [6 8 43 55 67 77 84 85 92] 67 ......
9. [6 8 43 55 67 67 77 84 85 92] ......

• 气泡排序法 顾名思义，就是排序时，最大的元素会如同气泡一样移至右端，其利用比较相邻元素的方法，将大的元素交换至右端，所以大的元素会不断的往右移动，直到适当的位置为止。

基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间，当寻访完阵列后都没有发生任何的交换动作，表示排序已经完成，而无需再进行之后的回圈比较与交换动作，例如： 排序前：95 27 90 49 80 58 6 9 18 50

1. 27 90 49 80 58 6 9 18 50 [95] 95浮出
2. 27 49 80 58 6 9 18 50 [90 95] 90浮出
3. 27 49 58 6 9 18 50 [80 90 95] 80浮出
4. 27 49 6 9 18 50 [58 80 90 95] ......
5. 27 6 9 18 49 [50 58 80 90 95] ......
6. 6 9 18 27 [49 50 58 80 90 95] ......
7. 6 9 18 [27 49 50 58 80 90 95] 由于接下来不会再发生交换动作，排序提早结束 在上面的例子当中，还加入了一个观念，就是当进行至i与i+1时没有交换的动作，表示接下来的i+2至n已经排序完毕，这也增进了气泡排序的效率。

实作

• C /#include /#include /#include /#define MAX 10 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} void selsort(int[]); // 选择排序 void insort(int[]); // 插入排序 void bubsort(int[]); // 气泡排序 int main(void) { int number[MAX] = {0}; int i; srand(time(NULL)); printf("排序前："); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } printf("\n请选择排序方式：\n"); printf("(1)选择排序\n(2)插入排序\n(3)气泡排序\n:"); scanf("%d", &i); switch(i) { case 1: selsort(number); break; case 2: insort(number); break; case 3: bubsort(number); break; default: printf("选项错误(1..3)\n"); } return 0; } void selsort(int number[]) { int i, j, k, m; for(i = 0; i < MAX-1; i++) { m = i; for(j = i+1; j < MAX; j++) if(number[j] < number[m]) m = j; if( i != m) SWAP(number[i], number[m]) printf("第 %d 次排序：", i+1); for(k = 0; k < MAX; k++) printf("%d ", number[k]); printf("\n"); } } void insort(int number[]) { int i, j, k, tmp; for(j = 1; j < MAX; j++) { tmp = number[j]; i = j - 1; while(tmp < number[i]) { number[i+1] = number[i]; i--; if(i == -1) break; } number[i+1] = tmp; printf("第 %d 次排序：", j); for(k = 0; k < MAX; k++) printf("%d ", number[k]); printf("\n"); } } void bubsort(int number[]) { int i, j, k, flag = 1; for(i = 0; i < MAX-1 && flag == 1; i++) { flag = 0; for(j = 0; j < MAX-i-1; j++) { if(number[j+1] < number[j]) { SWAP(number[j+1], number[j]); flag = 1; } } printf("第 %d 次排序：", i+1); for(k = 0; k < MAX; k++) printf("%d ", number[k]); printf("\n"); } }

• Java public class BasicSort { public static void selectionSort(int[] number) { for(int i = 0; i < number.length - 1; i++) { int m = i; for(int j = i + 1; j < number.length; j++) if(number[j] < number[m]) m = j; if(i != m) swap(number, i, m); } } public static void injectionSort(int[] number) { for(int j = 1; j < number.length; j++) { int tmp = number[j]; int i = j - 1; while(tmp < number[i]) { number[i+1] = number[i]; i--; if(i == -1) break; } number[i+1] = tmp; } } public static void bubbleSort(int[] number) { boolean flag = true; for(int i = 0; i < number.length-1 && flag; i++) { flag = false; for(int j = 0; j < number.length-i-1; j++) { if(number[j+1] < number[j]) { swap(number, j+1, j); flag = true; } } } } private static void swap(int[] number, int i, int j) { int t; t = number[i]; number[i] = number[j]; number[j] = t; } }

SeparateNumber

Algorithm Gossip: 数字拆解

说明

这个题目来自于 数字拆解，我将之改为C语言的版本，并加上说明。 题目是这样的： 3 = 2+1 = 1+1+1 所以3有三种拆法 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五种 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 共七种 依此类推，请问一个指定数字NUM的拆解方法个数有多少个？

解法

我们以上例中最后一个数字5的拆解为例，假设f( n )为数字n的可拆解方式个数，而f(x, y)为使用y以下的数字来拆解x的方法个数，则观察： 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 使用函式来表示的话： f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,4) + f(0,5) 其中f(1, 4) = f(1, 3) + f(1, 2) + f(1, 1)，但是使用大于1的数字来拆解1没有意义，所以f(1, 4) = f(1, 1)，而同样的，f(0, 5)会等于f(0, 0)，所以： f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0) 依照以上的说明，使用动态程式规画（Dynamic programming）来进行求解，其中f(4,1)其实就是f(5-1, min(5-1,1))，f(x, y)就等于f(n-y, min(n-x, y))，其中n为要拆解的数字，而min()表示取两者中较小的数。 使用一个二维阵列表格table[x][y]来表示f(x, y)，刚开始时，将每列的索引0与索引1元素值设定为1，因为任何数以0以下的数拆解必只有1种，而任何数以1以下的数拆解也必只有1种： for(i = 0; i < NUM +1; i++){ table[i][0] = 1; // 任何数以0以下的数拆解必只有1种 table[i][1] = 1; // 任何数以1以下的数拆解必只有1种 }

接下来就开始一个一个进行拆解了，如果数字为NUM，则我们的阵列维度大小必须为NUM x (NUM/2+1)，以数字10为例，其维度为10 x 6我们的表格将会如下所示： 1 1 0 0 0 0 1 1 0 0 0 0 1 1 2 0 0 0 1 1 2 3 0 0 1 1 3 4 5 0 1 1 3 5 6 7 1 1 4 7 9 0 1 1 4 8 0 0 1 1 5 0 0 0 1 1 0 0 0 0

实作

• C /#include /#include /#define NUM 10 // 要拆解的数字 /#define DEBUG 0 int main(void) { int table[NUM][NUM/2+1] = {0}; // 动态规画表格 int count = 0; int result = 0; int i, j, k; printf("数字拆解\n"); printf("3 = 2+1 = 1+1+1 所以3有三种拆法\n"); printf("4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1"); printf("共五种\n"); printf("5 = 4 + 1 = 3 + 2 = 3 + 1 + 1"); printf(" = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1"); printf("共七种\n"); printf("依此类推，求 %d 有几种拆法？", NUM); // 初始化 for(i = 0; i < NUM; i++){ table[i][0] = 1; // 任何数以0以下的数拆解必只有1种 table[i][1] = 1; // 任何数以1以下的数拆解必只有1种 } // 动态规划 for(i = 2; i <= NUM; i++){ for(j = 2; j <= i; j++){ if(i + j > NUM) // 大于 NUM continue; count = 0; for(k = 1 ; k <= j; k++){ count += table[i-k][(i-k >= k) ? k : i-k]; } table[i][j] = count; } } // 计算并显示结果 for(k = 1 ; k <= NUM; k++) result += table[NUM-k][(NUM-k >= k) ? k : NUM-k]; printf("\n\nresult: %d\n", result); if(DEBUG) { printf("\n除错资讯\n"); for(i = 0; i < NUM; i++) { for(j = 0; j < NUM/2+1; j++) printf("%2d", table[i][j]); printf("\n"); } } return 0; }

ShakerSort

Algorithm Gossip: Shaker 排序法 - 改良的气泡排序

说明

请看看之前介绍过的气泡排序法： for(i = 0; i < MAX-1 && flag == 1; i++) { flag = 0; for(j = 0; j < MAX-i-1; j++) { if(number[j+1] < number[j]) { SWAP(number[j+1], number[j]); flag = 1; } } }

事实上这个气泡排序法已经不是单纯的气泡排序了，它使用了旗标与右端左移两个方法来改进排序的效能，而Shaker排序法使用到后面这个观念进一步改良气泡排序法。

解法

在上面的气泡排序法中，交换的动作并不会一直进行至阵列的最后一个，而是会进行至MAX-i-1，所以排序的过程中，阵列右方排序好的元素会一直增加，使得左边排序的次数逐渐减少，如我们的例子所示： 排序前：95 27 90 49 80 58 6 9 18 50

1. 27 90 49 80 58 6 9 18 50 [95] 95浮出
2. 27 49 80 58 6 9 18 50 [90 95] 90浮出
3. 27 49 58 6 9 18 50 [80 90 95] 80浮出
4. 27 49 6 9 18 50 [58 80 90 95] ......
5. 27 6 9 18 49 [50 58 80 90 95] ......
6. 6 9 18 27 [49 50 58 80 90 95] ......
7. 6 9 18 [27 49 50 58 80 90 95] 方括号括住的部份表示已排序完毕，Shaker排序使用了这个概念，如果让左边的元素也具有这样的性质，让左右两边的元素都能先排序完成，如此未排序的元素会集中在中间，由于左右两边同时排序，中间未排序的部份将会很快的减少。 方法就在于气泡排序的双向进行，先让气泡排序由左向右进行，再来让气泡排序由右往左进行，如此完成一次排序的动作，而您必须使用left与right两个旗标来记录左右两端已排序的元素位置。 一个排序的例子如下所示： 排序前：45 19 77 81 13 28 18 19 77 11 往右排序：19 45 77 13 28 18 19 77 11 [81] 向左排序：[11] 19 45 77 13 28 18 19 77 [81] 往右排序：[11] 19 45 13 28 18 19 [77 77 81] 向左排序：[11 13] 19 45 18 28 19 [77 77 81] 往右排序：[11 13] 19 18 28 19 [45 77 77 81] 向左排序：[11 13 18] 19 19 28 [45 77 77 81] 往右排序：[11 13 18] 19 19 [28 45 77 77 81] 向左排序：[11 13 18 19 19] [28 45 77 77 81] 如上所示，括号中表示左右两边已排序完成的部份，当left > right时，则排序完成。

实作

• C /#include /#include /#include /#define MAX 10 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} void shakersort(int[]); int main(void) { int number[MAX] = {0}; int i; srand(time(NULL)); printf("排序前："); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } shakersort(number); printf("\n"); return 0; } void shakersort(int number[]) { int i, left = 0, right = MAX - 1, shift = 0; while(left < right) { // 向右进行气泡排序 for(i = left; i < right; i++) { if(number[i] > number[i+1]) { SWAP(number[i], number[i+1]); shift = i; } } right = shift; printf("\n往右排序："); for(i = 0; i < MAX; i++) printf("%d ", number[i]); // 向左进行气泡排序 for(i = right; i > left; i--) { if(number[i] < number[i-1]) { SWAP(number[i], number[i-1]); shift = i; } } left = shift; printf("\n向左排序："); for(i = 0; i < MAX; i++) printf("%d ", number[i]); } }

• Java public class ShakerSort { public static void sort(int[] number) { int i, left = 0, right = number.length - 1, shift = 0; while(left < right) { // 向右进行气泡排序 for(i = left; i < right; i++) { if(number[i] > number[i+1]) { swap(number, i, i+1); shift = i; } } right = shift; // 向左进行气泡排序 for(i = right; i > left; i--) { if(number[i] < number[i-1]) { swap(number, i ,i-1); shift = i; } } left = shift; } } private static void swap(int[] number, int i, int j) { int t; t = number[i]; number[i] = number[j]; number[j] = t; } }