生活随笔
收集整理的這篇文章主要介紹了
数据结构与算法--贪婪算法2
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
近似裝箱問題
-
解決裝箱問題（bin packing problem）的算法。也可以用貪婪算法來完成
-
給定N項物品，大小為s1，s2，s3…sn，所有的大小滿足0 < si < 1。問題是要把這些物品裝到最小數目的箱子中，已知每一個箱子容量是1個單位。我們用如下案例，有大小如下的物品：0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8的一列物品最優裝修辦法
-
有兩種結局方案：
- 一種聯機裝箱問題（online bin packing problem）。在這種問題中，每一件物品必須放入一個箱子之后才能處理下一個物品
- 第二中脫機裝箱問題（offline bin packing problem）。在一個脫機裝箱算法中，我們做任何事情都需要等所有的輸入數據全被讀取之后才進行
聯機算法
下項合適算法
public class KnapsackProblem {private static final int MAX_WEIGHT
= 10;public static int[] getSource(int num
) {int[] source
= new int[num
];Random random
= new Random();for (int i
= 0; i
< num
; i
++) {source
[i
] = random
.nextInt(10);System
.out
.println(source
[i
]);}return source
;}public static int[][] multiKnasack(int[] source
) {int num
= source
.length
;int[][] myPackage
= new int[num
][num
];int[] position
= new int[num
];int[] weight
= new int[num
];int packagePosition
= 0;for (int i
= 0; i
< source
.length
; i
++) {if (MAX_WEIGHT
- weight
[packagePosition
] < source
[i
]) {packagePosition
++;}myPackage
[packagePosition
][position
[packagePosition
]] = source
[i
];weight
[packagePosition
] += source
[i
];position
[packagePosition
] += 1;}return myPackage
;}public static void main(String
[] args
) {int[] source
= getSource(20);int[][] myPackage
= multiKnasack(source
);for (int i
= 0; i
< myPackage
.length
; i
++) {System
.out
.print("第" + i
+ "個箱子：");for (int i1
= 0; i1
< myPackage
[i
].length
; i1
++) {if (myPackage
[i
][i1
] > 0) {System
.out
.print(myPackage
[i
][i1
] + ", ");}}System
.out
.println();}}
}
- 下項合適算法有一個合理的性能保證，但是效果在實踐中很差，因為在不需要開普新箱子的時候他卻會開辟一個新的箱子。
首次合適算法
- 算法定義：有序掃描箱子，并把新的物品放入足夠能放下他的第一個箱子中。因此只有當前面那些放置物品的箱子已經容納不下當前物品的時候才會開辟新的箱子
- 算法實現：
public class KnapsackProblem {private static final int MAX_WEIGHT
= 10;public static int[] getSource(int num
) {int[] source
= new int[num
];Random random
= new Random();for (int i
= 0; i
< num
; i
++) {source
[i
] = random
.nextInt(10);System
.out
.println(source
[i
]);}return source
;}public static int[][] multiKnasackFirst(int[] source
){int num
= source
.length
;int[][] myPackage
= new int[num
][num
];int[] position
= new int[num
];int[] weight
= new int[num
];int packagePosition
= 0;for (int i
= 0; i
< source
.length
; i
++) {boolean isInsert
= false;for (int j
= 0; j
< weight
.length
; j
++) {if(MAX_WEIGHT
- weight
[j
] >= source
[i
]){isInsert
= true;myPackage
[j
][position
[j
]] = source
[i
];weight
[j
] += source
[i
];position
[j
] += 1;break;}}if(!isInsert
){packagePosition
++;myPackage
[packagePosition
][position
[packagePosition
]] = source
[i
];weight
[packagePosition
] += source
[i
];position
[packagePosition
] += 1;}}return myPackage
;}public static void main(String
[] args
) {int[] source
= getSource(20);int[][] myPackage
= multiKnasackFirst(source
);for (int i
= 0; i
< myPackage
.length
; i
++) {System
.out
.print("第" + i
+ "個箱子：");for (int i1
= 0; i1
< myPackage
[i
].length
; i1
++) {if (myPackage
[i
][i1
] > 0) {System
.out
.print(myPackage
[i
][i1
] + ", ");}}System
.out
.println();}}
}
最佳適合算法
package com
.ljm
.resource
.math
.greedy
;import java
.util
.Random
;
public class KnapsackProblem {private static final int MAX_WEIGHT
= 10;public static int[] getSource(int num
) {int[] source
= new int[num
];Random random
= new Random();for (int i
= 0; i
< num
; i
++) {source
[i
] = random
.nextInt(10);System
.out
.println(source
[i
]);}return source
;}public static int[][] multiKnasackBest(int[] source
){int num
= source
.length
;int[][] myPackage
= new int[num
][num
];int[] position
= new int[num
];int[] weight
= new int[num
];int packagePosition
= 0;for (int i
= 0; i
< source
.length
; i
++) {int maxWeight
= -1;int maxWeightId
= -1;for (int j
= 0; j
<= packagePosition
; j
++) {if(MAX_WEIGHT
- weight
[j
] > source
[i
]){if(weight
[j
] > maxWeight
){maxWeight
= weight
[j
];maxWeightId
= j
;}}}if(maxWeightId
< 0){packagePosition
++;myPackage
[packagePosition
][position
[packagePosition
]] = source
[i
];weight
[packagePosition
] += source
[i
];position
[packagePosition
] += 1;}else {myPackage
[maxWeightId
][position
[maxWeightId
]] = source
[i
];weight
[maxWeightId
] += source
[i
];position
[maxWeightId
] += 1;}}return myPackage
;}public static void main(String
[] args
) {int[] source
= getSource(20);int[][] myPackage
= multiKnasackBest(source
);for (int i
= 0; i
< myPackage
.length
; i
++) {System
.out
.print("第" + i
+ "個箱子：");for (int i1
= 0; i1
< myPackage
[i
].length
; i1
++) {if (myPackage
[i
][i1
] > 0) {System
.out
.print(myPackage
[i
][i1
] + ", ");}}System
.out
.println();}}
}
脫機算法
public class KnapsackProblem {private static final int MAX_WEIGHT
= 10;public static int[] getSource(int num
) {int[] source
= new int[num
];Random random
= new Random();for (int i
= 0; i
< num
; i
++) {source
[i
] = random
.nextInt(10);System
.out
.println(source
[i
]);}return source
;}public static int[][] multiknasackDecreasing(int[] source
){quickSort(source
, 0, source
.length
- 1);return multiKnasackFirst(source
);}public static void quickSort(int[] source
, int left
, int right
){if(left
> right
){int temp
= swap(source
, left
, right
);quickSort(source
, left
, temp
- 1);quickSort(source
, temp
+ 1, right
);}}public static int swap(int[] source
, int left
, int right
){if (left
< right
){int position
= source
[left
];while (left
< right
){while(left
< right
&& position
> source
[right
]){right
--;}if(left
< right
){source
[right
] = source
[left
];left
++;}while (left
< right
&& position
< source
[left
]){left
++;}if(left
< right
){source
[left
] = source
[right
];right
--;}}source
[left
] = position
;}return left
;}public static int[][] multiKnasackFirst(int[] source
){int num
= source
.length
;int[][] myPackage
= new int[num
][num
];int[] position
= new int[num
];int[] weight
= new int[num
];int packagePosition
= 0;for (int i
= 0; i
< source
.length
; i
++) {boolean isInsert
= false;for (int j
= 0; j
< weight
.length
; j
++) {if(MAX_WEIGHT
- weight
[j
] >= source
[i
]){isInsert
= true;myPackage
[j
][position
[j
]] = source
[i
];weight
[j
] += source
[i
];position
[j
] += 1;break;}}if(!isInsert
){packagePosition
++;myPackage
[packagePosition
][position
[packagePosition
]] = source
[i
];weight
[packagePosition
] += source
[i
];position
[packagePosition
] += 1;}}return myPackage
;}public static void main(String
[] args
) {int[] source
= getSource(20);int[][] myPackage
= multiknasackDecreasing(source
);for (int i
= 0; i
< myPackage
.length
; i
++) {System
.out
.print("第" + i
+ "個箱子：");for (int i1
= 0; i1
< myPackage
[i
].length
; i1
++) {if (myPackage
[i
][i1
] > 0) {System
.out
.print(myPackage
[i
][i1
] + ", ");}}System
.out
.println();}}
}
上一篇：數據結構與算法–貪婪算法
下一篇：數據結構與算法–分治算法
總結
以上是生活随笔為你收集整理的数据结构与算法--贪婪算法2的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
