(UVA) Dividing coins - Solution
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=503
The solution below used the concept of Knapsack, related to Dynamic Programming, to solve this problem.
import java.io.*;
import java.util.*;
class Main {
public int[][] matrix;
public int[] coins;
public int division;
public int knapsack(int volume, int index) {
if (volume == 0) {
return 2;
}
else if (volume < 0 || index < 0) {
return 1;
}
if (matrix[volume][index] != 0) {
return matrix[volume][index];
}
int use = knapsack(volume-coins[index], index-1);
int notUse = knapsack(volume, index-1);
matrix[volume][index] = Math.max(use, notUse);
return matrix[volume][index];
}
public static int reader(BufferedReader br) throws NumberFormatException, IOException {
int n;
int resp = 0;
while (true) {
n = br.read();
if (n >= '0' && n <= '9') {
break;
}
}
while (true) {
resp = resp*10 + n-'0';
n = br.read();
if (n < '0' || n > '9') {
break;
}
}
return resp;
}
public void process() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int numTests = reader(br);
for (int i = 0; i < numTests; i++) {
int totalCoins = 0;
int numCoins = reader(br);
coins = new int[numCoins];
if (numCoins == 0) {
bw.write("0\n");
continue;
}
for (int j = 0; j < numCoins; j++) {
coins[j] = reader(br);
totalCoins += coins[j];
}
int halfCoins = totalCoins/2;
int tmp = halfCoins;
int possible = 1;
while (possible != 2 && tmp >= 0) {
matrix = new int[tmp+1][numCoins];
possible = knapsack(tmp, numCoins-1);
tmp -= 1;
}
int firstDivision = tmp+1;
int secondDivision = totalCoins-firstDivision;
int result = Math.abs(secondDivision-firstDivision);
bw.write(result+"\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
The solution below used the concept of Knapsack, related to Dynamic Programming, to solve this problem.
import java.io.*;
import java.util.*;
class Main {
public int[][] matrix;
public int[] coins;
public int division;
public int knapsack(int volume, int index) {
if (volume == 0) {
return 2;
}
else if (volume < 0 || index < 0) {
return 1;
}
if (matrix[volume][index] != 0) {
return matrix[volume][index];
}
int use = knapsack(volume-coins[index], index-1);
int notUse = knapsack(volume, index-1);
matrix[volume][index] = Math.max(use, notUse);
return matrix[volume][index];
}
public static int reader(BufferedReader br) throws NumberFormatException, IOException {
int n;
int resp = 0;
while (true) {
n = br.read();
if (n >= '0' && n <= '9') {
break;
}
}
while (true) {
resp = resp*10 + n-'0';
n = br.read();
if (n < '0' || n > '9') {
break;
}
}
return resp;
}
public void process() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int numTests = reader(br);
for (int i = 0; i < numTests; i++) {
int totalCoins = 0;
int numCoins = reader(br);
coins = new int[numCoins];
if (numCoins == 0) {
bw.write("0\n");
continue;
}
for (int j = 0; j < numCoins; j++) {
coins[j] = reader(br);
totalCoins += coins[j];
}
int halfCoins = totalCoins/2;
int tmp = halfCoins;
int possible = 1;
while (possible != 2 && tmp >= 0) {
matrix = new int[tmp+1][numCoins];
possible = knapsack(tmp, numCoins-1);
tmp -= 1;
}
int firstDivision = tmp+1;
int secondDivision = totalCoins-firstDivision;
int result = Math.abs(secondDivision-firstDivision);
bw.write(result+"\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
Comments
Post a Comment