amit taneja
Ranch Hand
Posts: 817
posted 11 years ago
Hi,
can anybody explain the meaning of this programming problem please
Thanks

Problem Statement
����
You are given a set of twodimensional vectors in two int[]s  x and y (the ith elements of x and y represent x and y coordinates of the ith vector). Find a subset of the vectors such that the sum of all vectors in the subset has the maximum possible length. Return this length.
Definition
����
Class:
VectorSet
Method:
maxLength
Parameters:
int[], int[]
Returns:
double
Method signature:
double maxLength(int[] x, int[] y)
(be sure your method is public)
����
Notes

The sum of vectors (x1, y1) and (x2, y2) is the vector (x1+x2, y1+y2).

The length of vector (x, y) is the value sqrt(x * x + y * y).

The returned value must be accurate to within a relative or absolute value of 1E9.

The input (as well as the resulting subset) can contain equal vectors (see example 1).

Consider the entire set to be a subset.
Constraints

x will contain between 1 and 50 elements, inclusive.

x and y will contain the same number of elements.

Each element of x will be between 1000 and 1000, inclusive.

Each element of y will be between 1000 and 1000, inclusive.
Examples
0)
����
{0,0}
{1,1}
Returns: 1.0
Choose any one vector.
1)
����
{0, 0}
{1, 1}
Returns: 2.0
Choose two vectors. The sum is (0, 2).
2)
����
{0, 0, 1, 1}
{1, 1, 0, 0}
Returns: 1.4142135623730951
3)
����
{0, 0, 0, 0}
{1, 2, 1, 2}
Returns: 3.0
4)
����
{17,8,5,8,8,11,3,2,19,4,22,15,20,13,7,15,23,17,9,10,17,24,20,22,1,7,19,18,17}
{7,5,2,18,9,24,14,9,21,14,23,7,14,23,23,17,17,22,3,21,10,1,24,17,25,12,21,12,13}
Returns: 289.4563870430224
can anybody explain the meaning of this programming problem please
Thanks

Problem Statement
����
You are given a set of twodimensional vectors in two int[]s  x and y (the ith elements of x and y represent x and y coordinates of the ith vector). Find a subset of the vectors such that the sum of all vectors in the subset has the maximum possible length. Return this length.
Definition
����
Class:
VectorSet
Method:
maxLength
Parameters:
int[], int[]
Returns:
double
Method signature:
double maxLength(int[] x, int[] y)
(be sure your method is public)
����
Notes

The sum of vectors (x1, y1) and (x2, y2) is the vector (x1+x2, y1+y2).

The length of vector (x, y) is the value sqrt(x * x + y * y).

The returned value must be accurate to within a relative or absolute value of 1E9.

The input (as well as the resulting subset) can contain equal vectors (see example 1).

Consider the entire set to be a subset.
Constraints

x will contain between 1 and 50 elements, inclusive.

x and y will contain the same number of elements.

Each element of x will be between 1000 and 1000, inclusive.

Each element of y will be between 1000 and 1000, inclusive.
Examples
0)
����
{0,0}
{1,1}
Returns: 1.0
Choose any one vector.
1)
����
{0, 0}
{1, 1}
Returns: 2.0
Choose two vectors. The sum is (0, 2).
2)
����
{0, 0, 1, 1}
{1, 1, 0, 0}
Returns: 1.4142135623730951
3)
����
{0, 0, 0, 0}
{1, 2, 1, 2}
Returns: 3.0
4)
����
{17,8,5,8,8,11,3,2,19,4,22,15,20,13,7,15,23,17,9,10,17,24,20,22,1,7,19,18,17}
{7,5,2,18,9,24,14,9,21,14,23,7,14,23,23,17,17,22,3,21,10,1,24,17,25,12,21,12,13}
Returns: 289.4563870430224
Thanks and Regards, Amit Taneja
posted 11 years ago
Moving to the Java in General (beginner) forum.
To anybody that decides to help:
Please try to be as helpful as possible without providing complete solutions. In the long run these don't help anyone
Dave
To anybody that decides to help:
Please try to be as helpful as possible without providing complete solutions. In the long run these don't help anyone
Dave
Jaap Vermeer
Greenhorn
Posts: 16
posted 11 years ago
Here is a hint:
Brute force: Compute the length of all possibilities and choose the highest length.
You can do this recursively, by making a method that calls itself n (=arraylength) times each time removing one element from the arrays.
That way, you get n! (n * n1 * n2 * ... * 2 * 1) iterations.
Brute force: Compute the length of all possibilities and choose the highest length.
You can do this recursively, by making a method that calls itself n (=arraylength) times each time removing one element from the arrays.
That way, you get n! (n * n1 * n2 * ... * 2 * 1) iterations.