#java #algorithm #math #dynamic
Вопрос:
Я работаю над проектом на java. В этом я должен рассчитать самую высокую вероятность из списка списков.
Допустим, список есть probs = [[0.5, 0.5, 1],[0.25,0.1,0.75]] . probs-это список списков, где probs[i][j] представляет вероятность того, что растение i будет готово вовремя, если ему выделят j лампы. Значения в задачах находятся в диапазоне от 0 до 1 включительно.
Элементы в каждом списке представляют вероятность того, что растение вырастет, если мы используем такое количество ламп, например. в приведенном списке, если мы используем 0 ламп для завода 0, вероятность равна 0,5, Если мы используем 2 лампы в заводе 1, вероятность равна 0,75
Аналогично, если мы используем 10 списков с 10 элементами, такими как:
probs = [[0.92, 0.88, 0.07, 0.74, 0.83, 0.73, 0.85, 0.41, 0.94, 0.58, 0.17],
[0.05, 0.42, 0.01, 0.53, 0.03, 0.13, 0.49, 0.64, 0.13, 0.78, 0.05],
[0.68, 0.38, 0.86, 0.6, 0.53, 0.49, 0.89, 0.18, 0.69, 0.21, 0.3],
[0.61, 0.85, 0.17, 0.78, 0.21, 0.05, 0.09, 0.7, 0.08, 0.86, 0.21],
[0.72, 0.81, 0.12, 0.73, 0.45, 0.8, 0.3, 0.84, 0.89, 0.48, 0.33],
[0.19, 0.33, 0.01, 0.54, 0.71, 0.56, 0.55, 0.28, 0.29, 0.43, 0.42],
[0.36, 0.65, 0.38, 0.48, 0.05, 0.28, 0.45, 0.42, 0.49, 0.5, 0.97],
[0.95, 0.05, 0.73, 0.91, 0.25, 0.16, 0.11, 0.67, 0.48, 0.48, 0.77],
[0.96, 0.21, 0.19, 0.55, 0.04, 0.58, 0.91, 0.3, 0.92, 0.36, 0.48],
[0.46, 0.6, 0.76, 0.91, 0.79, 0.92, 0.66, 0.28, 0.48, 0.32, 0.17]]
В этом списке у нас 10 растений и 10 ламп. Таким образом, после расчета результат будет
allocation of lamps to plants: [0, 1, 0, 1, 0, 4, 1, 0, 0, 3]
best probability: 0.061589317090129915
Я не могу понять, как они выбирают, что эта проблема лучше всего подходит для этого растения. Я имею в виду, каковы будут критерии оценки для выбора наиболее подходящей задачи для этого растения из каждого списка в зависимости от количества ламп.
Что я сделал для этого, так это:
public static void best_lamp_allocation(int num_p, int num_l, ArrayList<ArrayList<Float>> probs) {
List<Float> prob_Values = new ArrayList<>();
List<Integer> index_values = new ArrayList<>();
for (int i = 0; i < probs.size(); i ) {
String value = probs.get(i).toString().replace("[", "").replace("]", "");
String[] individual_values = value.split(", ");
for (int j = 0; j < individual_values.length; j ) {
if (Float.parseFloat(individual_values[j]) >= 0.5) {
prob_Values.add(Float.parseFloat(individual_values[j]));
index_values.add(j);
break;
}
}
}
System.out.println("nLamps allocated: " index_values);
float max_prob = 1;
for (Float prob_value : prob_Values) {
max_prob *= prob_value;
}
System.out.println("Max probability: " max_prob);
}
Этот код работает, если минимальная вероятность для каждого растения в списке 2×2 равна 0,5, но не работает для других списков, таких как список 10 х 10.
Комментарии:
1. извините за использование этого, но это было рекомендовано автоматически.
2. Должно ли это общее количество ламп быть ровно 10 или не более 10? Это проблема динамического программирования. Возможно, вы захотите ознакомиться с этим сообщением CS stackexchange , посвященным версии «максимальная сумма» и ее адаптации.
3. @kcsquared количество ламп и количество растений зависит от входных данных пользователя. вы не можете превышать количество введенных пользователем ламп.
4. Наивный подход состоял бы в том, чтобы рассчитать все возможные комбинации, а затем использовать ту, которая имеет наименьшую вероятность. Другие возможности вполне доступны на сайте, посвященном математике
5. @SirHawrk какие комбинации нравятся? Я имею в виду, как получить эти комбинации. Любой пример, пожалуйста.
Ответ №1:
Предположим results , что это 2D-таблица и results[i][j] с наибольшей вероятностью подходит для i растений и не более j чем для ламп. вы можете легко заполнить results[0][j] и results[i][0] . для results[i][j] того, чтобы i, j > 0 вы могли заполнить его на основе предыдущей строки, т. е. results[i-1][0 to j] и предыдущей ячейки results[i][j-1]
- когда мы хотим заполнить
results[i][j]одно дело-смотреть в предыдущей строке , у меня есть высокая вероятность и количество светильников, используемый, чтобы получить, что вероятность для каждой ячейки, мы использовали эти данные, чтобы получить сколько огней я могу использовать для текущего растений и вычислить его вероятность, если мы будем использовать много ламп выберите наибольшей вероятностью, это кандидатm1. - другой случай-игнорировать добавленную лампу и просто использовать
results[i][j-1]вероятность и лампы. этоm2.
максимальное значение между этими 2 числами-это значение для results[i][j]
код:
static int argmax(double[] arr, int i, int j) {
double max = arr[0];
int re = 0;
for (int t = i; t < j 1; t ) {
if (arr[t] > max) {
max = arr[t];
re = t;
}
}
return re;
}
static double maxBetweenRange(double[] arr, int i, int j) {
double max = arr[i];
for (int t = i 1; t <= j; t ) {
if (arr[t] > max) {
max = arr[t];
}
}
return max;
}
public static Unit max(Unit... num) {
double max = Double.MIN_VALUE;
Unit res = null;
for (Unit v : num) {
if (v.prob > max) {
max = v.prob;
res = v;
}
}
return res;
}
public static class Unit {
public double prob;
public int lamp;
@Override
public String toString() {
return "Unit{"
"prob=" prob
", lamp=" lamp
'}';
}
}
public static Unit[][] getHighProb(double[][] probs, int userLamps) {
Unit[][] results = new Unit[probs.length][Math.min(userLamps 1, probs[0].length)];
for (int j = 0; j < results[0].length; j ) {
Unit u = new Unit();
u.prob = maxBetweenRange(probs[0], 0, j);
u.lamp = argmax(probs[0], 0, j);
results[0][j] = u;
}
for (int i = 1; i < results.length; i ) {
Unit u = new Unit();
u.prob = results[i - 1][0].prob * probs[i][0];
u.lamp = 0;
results[i][0] = u;
}
for (int i = 1; i < results.length; i ) {
for (int j = 1; j < results[0].length; j ) {
Unit current;
Unit[] beforeRow = results[i - 1];
Unit m1 = new Unit();
m1.prob = Double.MIN_VALUE;
m1.lamp = Integer.MIN_VALUE;
for (int k = j; k > 0; k--) {
Unit x = beforeRow[k];
int remainingLamps = j - x.lamp;
for (int l = 0; l <= remainingLamps; l ) {
if (x.prob * probs[i][l] > m1.prob) {
m1.prob = x.prob * probs[i][l];
m1.lamp = l x.lamp;
}
}
}
Unit m2 = new Unit();
m2.prob = results[i][j - 1].prob;
m2.lamp = results[i][j - 1].lamp;
current = max(m1, m2);
results[i][j] = current;
}
}
return results;
}
назови это так:
Unit[][] array = getHighProb(probs, 10);
вы можете легко найти самую высокую вероятность для i растений и j ламп. временная сложность O(PL^2) (#растения, #лампы). для 10 растений и 10 ламп у вас есть это:
array[9][10]= Unit{prob=0.061589317090129915, lamp=10}