Skip to main content

Factorials and Multiplication of arrays

No replies
unipex
Offline
Joined: 2013-04-22
Points: 0

Hello. I have the following problem. I don't know if it's a knapsack problem, or what problem it exactly is. My java skills are not the greatest, so please help. Here is the problem. Then, I will show you my code. My code is incomplete and does not solve this problem. I'll explain my coding later

[code=Java]

The purpose of this project is to make you familiar with Comparable interface. There is only one method to implement in this interface called compareTo(T o). T is the generic type that could be any class in java. When you define a data structure in java, you can provide this interface by adding implements clause to the end of class definition

class MyDataStructure implements Comparable {

// your data

public int compareTo(MyDataStructure other) {

}

}

After define the data structure, you can sort a List of your types using Collections.sort:

List list = ...
...
Collections.sort( list );

Homework

Doing homework often makes students understand knowledge deeply. As a student of UESTC, WCM usually has much homework to do. Every day he gets a set of problems from teachers. Problem i will taketi time to complete. Given a schedule (i.e., an ordering of the problems), let Ci denote the finishing time of problem i. For example, if problem j is the first to be done, we would have Cj = tj . Each problem i also has a given weight wi that represents its importance to the student's mastering of the correlative knowledge. He wants to order the problems to minimize the weighted sum of the completion times, namely w1C1 + w2C2 + w3C3… + wnCn.

You should design an efficient algorithm to solve this problem. That is, you are given a set of n problems with a processing time ti and a weighted wi for each problem. You want to order the problems so as to minimize the weighted sum of the completion times, Σ(i=1..n)wiCi.

Example: Suppose there are two problems: the first takes time t1=2 and has weight w1=12, while the second problem takes time t2=3 and has weight w2=4. Then doing problem 1 first would yield a weighted completion time of 12*2+4*5=44, while doing the second problem first would yield a larger weighted completion time of 4*3+12*5=72.Apparently, 44 is the minimum of the weighted sum of completion times, Σ(i=1..n)wiCi.
Input
The input contains an integer T on the first line, which indicates the number of test cases. Each test case consists of three lines. The first line contains one integer n,(0 < n ≤ 1000),which means the number of the problems. The second line contains n numbers, t1,t2,…,tn,(0 < ti ≤ 20), ti means the time problem i would take. The third line contains n numbers, w1,w2,…wn,(0 < wi ≤ 20), wi means the weight of problem i.
Output
For each test case output one line containing a single integer, which represents the minimum of the weighted sum of the completion times, Σ(i=1..n)wiCi.
Sample Input

1
2
2 3
12 4

Sample Output

44

Sample Input 2

2
3
4 2 1
7 8 2
5
7 2 1 9 12
5 5 4 1 2

Sample Output 2

71

144
[/code]

Now here is my coding, and I will explain it:

[code=Java]

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public abstract class Homework implements Comparable {

@Override
public final int compareTo(final Homework other) {
// TODO Auto-generated method stub
return 0;
}

public static int calculate(final int count, final Integer[][] timeWeight) {
int time = 0;
int a = 0;
int sum = 0;

for (int i = 0; i < count; i++) {
time = time + timeWeight[0][a];

int temp = time * timeWeight[1][a];

sum = sum + temp;

a++;
}

return sum;
}

public static void main(final String[] args) {
final Scanner sc = new Scanner(System.in);

final int testCases = sc.nextInt();

int i = 0;
Integer[] problems;
Integer[][] timeWeight;
final Integer[] solution = new Integer[testCases];

List list = new ArrayList();

while (i < testCases) {
problems = new Integer[testCases];
problems[i] = sc.nextInt();

timeWeight = new Integer[problems[i]][problems[i]];

for (int a = 0; a < problems[i]; a++) {
for (int b = 0; b < problems[i]; b++) {
timeWeight[a][b] = sc.nextInt();
}
}

final int count = problems[i];

final int sumTotal = calculate(count, timeWeight);
list.add(sumTotal);

solution[i] = list.get(i);

for (int d = 0; d

}

i++;
}

for (int count1 = 0; count1 < testCases; count1++) {
System.out.println();
System.out.println(solution[count1]);
System.out.println();
}

}

}
[/code]

My logic and thinking is that within the while loop, I will grab all the input and solve it for one test loop. I will then store that solution in an array of solutions. Then when the while loop loops again, it will write over the previous array data and solve a new problem. Then I will also store that answer in the array of solutions. Then I will just print out the array of solutions. But for the problem, you have to find the smallest answer, using the different combinations. So with three problems, there is a total of 6 different combinations, because it's just 3 factorial. I have a 2D array, with time and weight. How do I multiply the 6 different combinations with 3 inputs, using the arrays. The question says to use List, and use the Collections class to sort it in different ways. Eclipse is giving me an error when I use "List list = new ArrayList ()" . I can't add the data when I say "list.add()". With Collections, I can reverse the order of data, insert elements at certain places, etc. But with arraylist, I am limited.

Also, for my logic on solving this problem, say I have 3 input. My solution was to rotate the elements (n-1) times. For example, for "1 2 3" input, I'll rotate it twice: "2 3 1" and "3 1 2". That's three combinations there. Then for "1 2 3", I'll switch the first element with the second, then first with third, then second with third. I'll also do this for the "2 3 1" and "3 1 2" combinations. They I'll calculate the sums with these 12 combinations (for 3 inputs, it's 28 combinations with 4 inputs), and just store all the answers. Then I will use Collections.sort to sort it least to greatest. Then I will grab the least and that will be my answer. But this sounds too complicated, and my stupid cocky stuck up professor keeps on saying that this is such an easy problem and it requires a little thinking. Please help. I am willing to completely change my program to solve this.