Hi,
I was wondering if anyone can help me translate this into java.
Thanks
#include "Element.h"
#include <stdlib.h>
element * Element(int s1, int w1, double c1, int x1, int k1)
{
element * retval = malloc(sizeof(element));
retval->s = s1;
retval->w = w1;
retval->c = (float) s1 / (float) w1;
retval->x = x1;
retval->k = k1;
return retval;
}typedef struct
{
int s; //value of coin
int w; // weight of coin
float c; // (s / w)
int x; // number of coin to be used
int k; // index of coin of this value in S[n]
} element;
element * Element(int s1, int w1, double c1, int x1, int k1);#include "externals.h"
int B = 7;
int n = N;
int S[N] = {4, 1, 3};
int X[N];
int W[N];
element * A[N];
element * Solution[N];#include "Element.h"
#include <stdlib.h>
#include <stdio.h>
#define N 3
#define new
#define BOOL int
#define FALSE 0
#define TRUE 1
extern int B;
extern int n;
extern int S[N];
extern int X[N];
extern int W[N];
extern element * A[N];
extern element * Solution[N];#include "functions.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/**************************************************************
Algorithm: Sort
Parameters: an array of pointers to element objects.
Description: algorithm looks at the "value density" (c) of
the objects and sorts them upon that parameter
in non-increasing order.
Side Effects: algorithm modifies global array "A"
parameter is technically not used, but
replacement of "A" with the parameter
will cause effect to be on the parameter
this is strictly unecessary in this particular
algorithm
**************************************************************/
void Sort(element * array[])
{
element * largest;
int i, j;
for (i = 0; i < n; i++)
{
largest = A[i];
for (j = i; j < n; j++)
{
if (A[j]->c > largest->c)
{
largest = A[j];
A[j] = A[i];
A[i] = largest;
}
}
}
}
/**************************************************************
Algorithm: Greedy
Parameters: A "remainder" (number to be consumed), and an
integer "i" marked as a starting index for
manipulations on global array.
Description: A greedy algorithm to increase the concentrations
of each object in the sorted array to consume as
much of the remainder as possible given the
starting element lovcated at the index.
Side Effects: The algorithm modifies both global arrays "A"
(necessarily) and "Solution" (conditionally).
Producing viable solutions to the value partitioning
problem, and replacing the global solution
if the local one is more efficient based on the
constraints of the problem.
**************************************************************/
void Greedy(int remainder, int i)
{
int number;
number = floor(remainder / A[i]->s);
A[i]->x = number;
if (totalValue(A, 0, N-1) == B)
{
if (!Solution[0] || totalWeight(A, 0, N-1) < totalWeight(Solution, 0, N-1))
{
copyArr(A, Solution);
}
return;
}
else if (i == (N-1))
{
return;
}
else
{
Greedy((remainder % A[i]->s), (i+1));
}
}
/**************************************************************
Algorithm: Backtrack
Parameters: Integers "start" and "stop" marking the indicies
of the global array "A" over which the algorithm
will operate during its call.
Description: A backtracking algorithm, assuming a pre-sorted
array in "locally greedy" (between the indicies)
concentrations. The algorithm moves slowly between
start and stop, from right to left, decrementing
the concentration of the object at the current
index, calling Greedy() from that point. This
forces a trace over the entire permutation space
of all viable solutions. Comparisons to the global
solution array, as described in documentation above,
are performed in Greedy(). The algorithm recurses
until the entire solution space between the indicies
is mapped. Then returns control to the calling
function. (In terminus, main())
Side Effects: The algorithm modifies global array "A" directly
and "Solution" indirectly by calling Greedy()
which has this known side effect.
**************************************************************/
void Backtrack(int stop, int start)
{
int dec_pos = start;
while (TRUE)
{
if (dec_pos < 0)
{
return;
}
if (A[dec_pos]->x != 0)
{
A[dec_pos]->x--;
}
else
{
dec_pos--;
continue;
}
Greedy(B-totalValue(A, 0, dec_pos), (dec_pos + 1));
Backtrack((dec_pos + 1), N-2);
if (dec_pos != stop)
{
dec_pos--;
}
else
{
break;
}
}
}
/**************************************************************
Algorithm: totalValue
Parameters: An array of pointers to element objects
two integers start and end.
Description: Computes the total value of the objects between
the indicies given their concentrations and
individual values.
Side Effects: None
**************************************************************/
int totalValue(element * array[], int start, int end)
{
register int i;
int total = 0;
element * e;
for (i = start; i <= end ; i++)
{
e = array[i];
total += e->s * e->x;
}
return total;
}
/**************************************************************
Algorithm: totalWeight
Parameters: An array of pointers to element objects
two integers start and end.
Description: Computes the total weight of the objects between
the indicies given their concentrations and
individual weights.
Side Effects: None
**************************************************************/
int totalWeight(element * array[], int start, int end)
{
register int i;
int total = 0;
element * e;
for (i = start; i <= end ; i++)
{
e = array[i];
total += e->w * e->x;
}
return total;
}
//prints the entire array to STDIO
void printArr(element * array[])
{
register int i = 0;
for (i = 0; i < N; i++)
{
printf("%i, ", array[i]->x);
}
printf("\n");
}
//prints elements and their values to STDIO, used for debugging and for useful info
void printElements(element * array[])
{
register int i;
for (i = 0; i < N; i++)
{
printf("%i:\n\t%i\n\t%i\n\t%i\n\t%f\n\n", i, array[i]->s, array[i]->w, array[i]->k, array[i]->c);
}
}
//copies the contents of one array of element objects into another to preserve the values.
void copyArr(element * source[], element * target[])
{
register int i = 0;
for (i = 0; i < N; i++)
{
element * old_e = source[i];
element * new_e = new Element(old_e->s, old_e->w, old_e->c, old_e->x, old_e->k);
target[i] = new_e;
}
}
/**************************************************************
Algorithms: initialization functions
Parameters: None
Description: Computes the weight values for each object based
on the total function w() given as input in this
assignment. The array of objects "A" is constructed.
The first element in "Solution" is set to NULL to
prevent a segfault when first checking against the
total weight in Greedy().
Side Effects: Global arrays W, A, and Solution are modified.
**************************************************************/
void initialize()
{
Solution[0] = NULL;
initialize_W();
initialize_A();
}
void initialize_A()
{
register int i;
for (i = 0; i < N; i++)
{
A[i] = new Element(S[i], W[i], 1, 0, i);
}
}
void initialize_W()
{
register int i;
for (i = 0; i < N; i++)
{
W[i] = w(S[i]);
}
}
//total function w given in the assignment, this can be any total function on the set of real integers
//it is currently set to return 1, as the last step in debugging was to check the condition for objects
//with equal weight.
int w(int s)
{
return 1;
}#include "externals.h"
void Sort(element * array[]);
void Greedy(int remainder, int i);
void Backtrack(int stop, int start);
int totalValue(element * array[], int start, int end);
int totalWeight(element * array[], int start, int end);
void printArr(element * array[]);
void printElements(element * array[]);
void copyArr(element * source[], element * target[]);
void initialize();
void initialize_A();
void initialize_W();
int w(int s);#include <stdio.h>
#include "functions.h"
int main (int argc, const char * argv[])
{
initialize();
Sort(A);
printElements(A);
Greedy(B, 0);
Backtrack(0, N-2);
if (totalValue(Solution, 0, N-1) != B)
{
printf("No Solution\n");
}
else
{
printArr(Solution);
}
return 0;
}
