Реализация c ++ выглядит нормально.
Ваши значения и веса, которые являются одномерным массивом в вашей текущей реализации PHP, станут 2-мерными.
Так, например,
values[i][j] будет значением j й предмет в классе i. Аналогично в случае weights[i][j]. Вы будете брать только один элемент для каждого класса i и продвигаться вперед, максимизируя условие.
Реализация c ++ также выполняет оптимизацию в memo. Он содержит только 2 массива размера, соответствующих условию max_weight, которые являются текущими и предыдущими состояниями. Это потому, что вам нужны только эти 2 состояния одновременно для вычисления текущего состояния.
Ответы на ваши сомнения:
1)
Моей первой мыслью было добавить массив class (k), отсортировать элементы по классу (k), и, когда мы решим выбрать элемент, который совпадает со следующим, проверить, лучше ли сохранить текущий элемент или элемент без следующего элемента. Выглядело многообещающе, но развалилось после проверки нескольких предметов. Примерно так: $ tempVal3 = $ value [$ n] + KSTest ($ n-2, $ c - $ weight [$ n]); max ($ tempVal2, $ tempVal3);
Это не сработает, потому что в классе k + 1 может быть какой-то элемент, в котором вы берете оптимальное значение и для соблюдения ограничения вам нужно принять неоптимальный значение для класса к. Таким образом, сортировка и выбор лучших не будет работать, когда ограничение достигнуто. Если ограничение не выполнено, вы всегда можете выбрать лучшее значение с лучшим весом.
2)
Другая мысль состоит в том, что при вызове функции я мог бы вызвать al oop для каждого типа класса и решить KS только с 1 элементом за один раз этого типа + остальные значения.
Да, вы находитесь на правильном пути здесь. Вы будете предполагать, что вы уже решили для первых k классов. Теперь вы попробуете расширить, используя значения класса k + 1 с учетом ограничения по весу.
3)
... но я не могу понять, где находится ограничение класса что происходит?
for (int i = 1; i < weight.size(); ++i) {
fill(current.begin(), current.end(), -1);
for (int j = 0; j < weight[i].size(); ++j) {
for (int k = weight[i][j]; k <= max_weight; ++k) {
if (last[k - weight[i][j]] > 0)
current[k] = max(current[k],
last[k - weight[i][j]] + value[i][j]);
}
}
swap(current, last);
}
В приведенном выше фрагменте кода c ++ первый l oop выполняет итерации по классу, второй l oop выполняет итерации по значениям класса, а третий l oop расширяет текущее состояние current с использованием предыдущего состояния last и только 1 элемент j с классом i одновременно. Поскольку вы используете только предыдущее состояние last и 1 элемент текущего класса для расширения и максимизации, вы соблюдаете ограничение.
Сложность времени:
O (total_items x max_weight) , что эквивалентно O (класс *) 1060 * x max_number_of_items_in_a_class x max_weight)