Here is my code, I did a DP function, but the thing is that some cases give a wrong answer, where is my mistake?
- Code: Select all
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Lectura leer = new Lectura("entrada.txt");
leer.Abrir();
int casos = leer.getCasos();
//System.out.println(casos);
String parte1=leer.getParte1();
//System.out.println(parte1);
String parte2=leer.getParte2();
//System.out.println(parte2);
ArrayList dinamico1 = new ArrayList();
ArrayList dinamico2 = new ArrayList();
Scanner scan1 = new Scanner(parte1);
Scanner scan2 = new Scanner(parte2);
while(scan1.hasNext()){
dinamico1.add(scan1.nextLine());
}
//System.out.println(dinamico1);
while(scan2.hasNext()){
dinamico2.add(scan2.nextLine());
}
//System.out.println(dinamico2);
for(int i=0;i<casos;i++){
int cantidad = Integer.parseInt(dinamico1.get(i).toString());
if(cantidad<=50){
//System.out.println(cantidad);
String dato = dinamico2.get(i).toString();
//System.out.println(dato);
int largo=cantidad;
int[] sticks = new int[largo];
int k=0;
StringTokenizer token = new StringTokenizer(dato);
while(token.hasMoreTokens()){
String aux=token.nextToken();
int aux1=Integer.parseInt(aux);
sticks[k]=aux1;
k++;
}
int[] sticksAnterior = sticks;
Quicksort quick = new Quicksort();
quick.ordena(sticks);
int max = sticks[0];
int suma = 0;
//System.out.println(max);
for(int j=0;j<sticks.length;j++){
suma = suma + sticks[j];
}
//System.out.println(sum);
for(int meta = max; meta<=suma;meta++){
if(suma%meta==0){
int particiones = suma/meta;
if(particiones(sticks,particiones)){
System.out.println(meta);
break;
}
}
}
}
else
{
System.out.println("ERROR");
}
}
}
static boolean particiones(int [] sticks, int partes){
int n=sticks.length;
boolean M[]= new boolean[partes+1];
M[1]=true;
for(int i=1;i<n;i++){
for(int j=sticks[i];j<partes+1;j++){
M[j]=M[j]||M[j-sticks[i]];
}
}
return M[partes];
}
}
Thank you