2012 7 26 (sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2012/index.html
5 2
3
4
- 5
.. 6
- 7
public class KnapsackBB { // 0-1 private static double maxsofar; private static boolean[] result; private static boolean[] choice; private static void backtrack(int i, double profit, double weight){ if(i >= (items.length-1)){ if(profit > maxsofar){ maxsofar = profit; result = choice.clone(); // else { if(items[i].getweight() <= weight){ choice[i] = true; // i backtrack(i + 1, profit + items[i].getprofit(), weight - items[i].getweight()); double z = 0; double u = weight; int j; for(j = i+1; items[j].getweight() <= u; j++){ u -= items[j].getweight(); z += items[j].getprofit(); z += u*items[j].getvalue(); if((z + profit) > maxsofar){ choice[i] = false; // i backtrack(i+1, profit, weight); 0-1 8
private static ItemBB[] items = { new ItemBB(" ", 10, 100), new ItemBB(" ", 98, 300), new ItemBB(" ", 398, 300), new ItemBB(" ", 1000, 6000), new ItemBB(" ", 398, 800), new ItemBB(" ", 100, 200), new ItemBB(" ", 200, 300), new ItemBB(" ", 980, 2000), new ItemBB(" ", 298, 400), new ItemBB(" ", 1000, 800), new ItemBB(" ", 10, 50), new ItemBB(" ", 20, 60), new ItemBB(" ", 100, 300), new ItemBB(" ", 20, 100), new ItemBB(" ", 100, 250), new ItemBB(" ", 300, 90), new ItemBB(" ", 333, 600), new ItemBB(" ", 198, 300), new ItemBB(" ", 300, 100), new ItemBB(" ", 1000, 200), new ItemBB(" ", 0, Double.POSITIVE_INFINITY) ;, 1000.0, 800.0 public static void main(string[], args) 298.0, { 400.0 double limit;, 200.0, 300.0 try {, 333.0, 600.0 limit = Double.parseDouble(args[0]); catch(exception e){ limit = 9000; Arrays.sort(items); maxsofar = Double.NEGATIVE_INFINITY;, 1000.0, 200.0 choice = new boolean[items.length];, 300.0, 90.0, 300.0, 100.0 backtrack(0, 0, limit); double p = 0, w = 0; int n = 0; for(int i = 0; i < items.length-1; i++){ if(result[i]){ p += items[i].getprofit(); w += items[i].getweight(); n++; System.out.println(items[i]); System.out.print(" : " + limit); System.out.print("\t : " + n); System.out.print("\t : " + w); System.out.println("\t : " + p); [sakai@star bin]$ java complex.knapsackbb 5000, 1000.0, 200.0, 300.0, 90.0, 300.0, 100.0, 398.0, 300.0, 100.0, 200.0, 980.0, 2000.0 : 5000.0 : 10 : 4990.0 : 4909.0 [sakai@star bin]$ java complex.knapsackbb 4900, 398.0, 300.0, 1000.0, 800.0, 298.0, 400.0, 200.0, 300.0, 333.0, 600.0, 980.0, 2000.0, 20.0, 60.0, 10.0, 50.0 : 4900.0 : 11 : 4900.0 : 4839.0 9
10
public class KnapsackDP { // private static void solve(itemdp[] items, int weight, int[] result){ double[] gain = new double[weight+1]; int[] choice = new int[weight+1]; Arrays.fill(choice, -1); - for(int j = 0; j < items.length; j++){ for(int i = 1; i <= weight; i++){ int k = i - items[j].getweight(); if(k >= 0){ if((gain[k] + items[j].getprofit()) > gain[i]){ gain[i] = gain[k] + items[j].getprofit(); choice[i] = j; int k; for(int i = weight; choice[i] >= 0; i -= items[k].getweight()){ k = choice[i]; result[k]++; 11
[sakai@star bin]$ java complex.knapsackdp 1200, 297.0, 298, 4 : 1200 : 4 : 1192 : 1188.0 [sakai@star bin]$ java complex.knapsackdp 1190, 297.0, 298, 3 public static, void main(string[] 288.0, args) 278, { 1 int limit; : 1190 : 4 : 1172 : 1179.0 try { limit = Integer.parseInt(args[0]); [sakai@star bin]$ java complex.knapsackdp 1170 catch(exception e){ limit = 9000;, 297.0, 298, 2, 288.0, 278, 2 int[] result : = new int[items.length]; 1170 : 4 : 1152 : 1170.0 solve(items, limit, result); [sakai@star bin]$ java complex.knapsackdp 1150 double p = 0; int w = 0, n, = 0; 297.0, 298, 1 for(int i =, 0; i < result.length; 288.0, i++){ 278, 3 if(result[i] : > 0){ 1150 : 4 : 1132 : 1161.0 p += items[i].getprofit()*result[i]; [sakai@star bin]$ java complex.knapsackdp 1130 w += items[i].getweight()*result[i];, 288.0, 278, 4 n += result[i]; : 1130 : 4 : 1112 : 1152.0 System.out.println(items[i] [sakai@star bin]$ java + ", " complex.knapsackdp + result[i]); 1110, 297.0, 298, 1 System.out.print(" :, 300.0, 398, " + limit); 2 System.out.print("\t : : 1110 " + n); : 3 : 1094 : 897.0 System.out.print("\t : [sakai@star bin]$ java " + w); complex.knapsackdp 1093 12 System.out.println("\t :, 297.0, 298, 2 " + p);, 300.0, 398, 1 : 1093 : 3 : 994 : 894.0 private static ItemDP[] items = { new ItemDP(" ", 297, 298), new ItemDP(" ", 280, 298), new ItemDP(" ", 295, 335), new ItemDP(" ", 283, 350), new ItemDP(" ", 291, 398), new ItemDP(" ", 270, 350), new ItemDP(" ", 288, 278), new ItemDP(" ", 300, 398), new ItemDP(" ", 265, 298), new ItemDP(" ", 290, 348) ;
13
d AB + d BC d AC 14
1. 2. 3. 4. 1. 2. 3. 15
16
17
: : : : ( ) PHS 18