blob: 07ffdcda0f6043ea2f057d814b65c28e3a2e3646 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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("");
}
}
|
