Discrete : add 01-knapsack assignment

1 files changed, 91 insertions, 0 deletions

diff --git a/01-knapsack/Solver.java b/01-knapsack/Solver.java
new file mode 100644
index 0000000..07ffdcd
--- /dev/null
+++ b/01-knapsack/Solver.java
@@ -0,0 +1,91 @@
+import java.io.*;
+import java.util.List;
+import java.util.ArrayList;
+
+/**
+ * The class <code>Solver</code> is an implementation of a greedy algorithm to solve the knapsack problem.
+ *
+ */
+public class Solver {
+    
+    /**
+     * The main class
+     */
+    public static void main(String[] args) {
+        try {
+            solve(args);
+        } catch (IOException e) {
+            e.printStackTrace();
+        }
+    }
+    
+    /**
+     * Read the instance, solve it, and print the solution in the standard output
+     */
+    public static void solve(String[] args) throws IOException {
+        String fileName = null;
+        
+        // get the temp file name
+        for(String arg : args){
+            if(arg.startsWith("-file=")){
+                fileName = arg.substring(6);
+            } 
+        }
+        if(fileName == null)
+            return;
+        
+        // read the lines out of the file
+        List<String> lines = new ArrayList<String>();
+
+        BufferedReader input =  new BufferedReader(new FileReader(fileName));
+        try {
+            String line = null;
+            while (( line = input.readLine()) != null){
+                lines.add(line);
+            }
+        }
+        finally {
+            input.close();
+        }
+        
+        
+        // parse the data in the file
+        String[] firstLine = lines.get(0).split("\\s+");
+        int items = Integer.parseInt(firstLine[0]);
+        int capacity = Integer.parseInt(firstLine[1]);
+
+        int[] values = new int[items];
+        int[] weights = new int[items];
+
+        for(int i=1; i < items+1; i++){
+          String line = lines.get(i);
+          String[] parts = line.split("\\s+");
+
+          values[i-1] = Integer.parseInt(parts[0]);
+          weights[i-1] = Integer.parseInt(parts[1]);
+        }
+
+        // a trivial greedy algorithm for filling the knapsack
+        // it takes items in-order until the knapsack is full
+        int value = 0;
+        int weight = 0;
+        int[] taken = new int[items];
+
+        for(int i=0; i < items; i++){
+            if(weight + weights[i] <= capacity){
+                taken[i] = 1;
+                value += values[i];
+                weight += weights[i];
+            } else {
+                taken[i] = 0;
+            }
+        }
+        
+        // prepare the solution in the specified output format
+        System.out.println(value+" 0");
+        for(int i=0; i < items; i++){
+            System.out.print(taken[i]+" ");
+        }
+        System.out.println("");        
+    }
+}
\ No newline at end of file