UriSteiff

knapsack

May 15th, 2021
475
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package il.ac.tau.cs.sw1.ex7;
  2. import java.util.*;
  3.  
  4. public class FractionalKnapSack implements Greedy<FractionalKnapSack.Item>{
  5.     int capacity;
  6.     List<Item> lst;
  7.  
  8.     FractionalKnapSack(int c, List<Item> lst1){
  9.         capacity = c;
  10.         lst = lst1;
  11.     }
  12.  
  13.     public static class Item {
  14.         double weight, value;
  15.         Item(double w, double v) {
  16.             weight = w;
  17.             value = v;
  18.         }
  19.  
  20.         @Override
  21.         public String toString() {
  22.             return "{" + "weight=" + weight + ", value=" + value + '}';
  23.         }
  24.     }
  25.    
  26.     public class ItemComparator implements Comparator<Item> {
  27.         @Override
  28.         public int compare(Item item1, Item item2) {
  29.             double item1RelativeValue = item1.value / item1.weight;
  30.             double item2RelativeValue = item2.value / item2.weight;
  31.             return Double.compare(item2RelativeValue, item1RelativeValue);
  32.         }
  33.     }
  34.    
  35.     public double weightSum(List<Item> candidates_lst) {
  36.         double weightSum = 0;
  37.         for (Item item: candidates_lst) {
  38.             weightSum += item.weight;
  39.         }
  40.         return weightSum;
  41.     }
  42.  
  43.     @Override
  44.     public Iterator<Item> selection() {
  45.         ArrayList<Item> items = new ArrayList<Item>(); // empty list of items
  46.         for (Item item: this.lst) { // add items
  47.             items.add(item);   
  48.         }
  49.         ItemComparator comp = new ItemComparator();
  50.         Collections.sort(items, comp); // descending order
  51.         return items.iterator(); // return iterator
  52.     }
  53.  
  54.     @Override
  55.     public boolean feasibility(List<Item> candidates_lst, Item element) {
  56.         return this.capacity > weightSum(candidates_lst);
  57.     }
  58.  
  59.     @Override
  60.     public void assign(List<Item> candidates_lst, Item element) {
  61.         if (weightSum(candidates_lst) + element.weight <= this.capacity) {
  62.             candidates_lst.add(element);
  63.         }
  64.         else {
  65.             double partial_weight = this.capacity - weightSum(candidates_lst);
  66.             Item partialItem = new Item(partial_weight, element.value);
  67.             candidates_lst.add(partialItem);
  68.         }
  69.     }
  70.  
  71.     @Override
  72.     public boolean solution(List<Item> candidates_lst) {
  73.         return this.capacity == weightSum(candidates_lst);
  74.     }
  75.    
  76.     public static void main(String[] args) {
  77.         Item item1 = new Item(30, 120);
  78.         Item item2 = new Item(20, 100);
  79.         Item item3 = new Item(10, 60);
  80.         List<Item> items = new ArrayList<Item>();
  81.         items.add(item1);
  82.         items.add(item2);
  83.         items.add(item3);
  84.         FractionalKnapSack sack = new FractionalKnapSack(50, items);
  85.         System.out.println(sack.greedyAlgorithm().toString());
  86.        
  87.     }
  88. }
  89.  
RAW Paste Data