В Java, как мне создать растровое изображение, чтобы решить "затруднительное положение рюкзака"

Question

Я нахожусь на моем первом курсе программирования, и я сейчас застрял.По сути, мы берем 16 значений из текстового файла (в первой строке кода), а во второй строке кода есть одно значение.Мы читаем эти 16 значений в массив и устанавливаем это значение 2-й строки в качестве нашей цели.У меня не было проблем с этой частью.

Но у меня возникли проблемы с созданием растрового изображения для проверки каждого возможного подмножества из 16 значений, которые равны целевому числу.

IE, скажем, у нас были эти числа:

12   15   20   4   3   10   17   12   24   21   19   33   27   11   25   32

Затем мы сопоставляем каждое значение с битовой картой

 0    1    1   0   0    0    0    1    1    1    0    1    0    0    1    0

Тогда мы принимаем только значения, предсказанные с "1"

     15   20                     12   24   21        33             25

Затем мы проверяем это подмножество, чтобы увидеть, равно ли оно целевому числу.

Нам разрешено использовать только один массив в задаче, и нам не разрешеноиспользовать математический класс (еще не дошел до него).

Я понимаю концепцию и знаю, что мне нужно реализовать операторы смещения и логический знак &, но я действительно вутрата.Я очень расстроен, и мне просто интересно, кто-нибудь может дать мне какие-нибудь советы.

Answer 1

Есть несколько шагов для решения этой проблемы. Для начала нужно перечислить все возможные битовые карты. Как уже отмечали другие, вы можете легко сделать это, увеличив целое число от 0 до 2 ^ n - 1.

Получив это, вы можете перебрать все возможные битовые карты, вам просто нужен способ взять эту битовую карту и "применить" ее к массиву, чтобы сгенерировать сумму элементов по всем индексам, представленным картой. Следующий метод является примером того, как это сделать:

private static int bitmapSum(int[] input, int bitmap) {
    // a variable for holding the running total
    int sum = 0;

    // iterate over each element in our array
    // adding only the values specified by the bitmap
    for (int i = 0; i < input.length; i++) {
        int mask = 1 << i;
        if ((bitmap & mask) != 0) {
            // If the index is part of the bitmap, add it to the total;
            sum += input[i];
        }
    }

    return sum;
}

Эта функция принимает массив целых чисел и битовую карту (представленную как целое число) и возвращает сумму всех элементов в массиве, чей индекс присутствует в маске.

Ключом к этой функции является возможность определить, присутствует ли данный индекс в битовой карте. Для этого сначала нужно создать битовую маску для нужного индекса, а затем применить эту маску к битовой карте, чтобы проверить, установлено ли это значение.

По сути, мы хотим построить целое число, в котором установлен только один бит, а все остальные равны нулю. Затем мы можем поразрядно И эту маску с битовой картой и проверить, установлена ​​ли конкретная позиция, сравнивая результат с 0.

Допустим, у нас есть 8-битная карта, подобная следующей:

map:       1 0 0 1 1 1 0 1
           ---------------
indexes:   7 6 5 4 3 2 1 0

Чтобы проверить значение для индекса 4, нам понадобится битовая маска, которая выглядит следующим образом:

mask:      0 0 0 1 0 0 0 0
           ---------------
indexes:   7 6 5 4 3 2 1 0

Чтобы построить маску, мы просто начинаем с 1 и сдвигаем ее на N:

1:            0 0 0 0 0 0 0 1
shift by 1:   0 0 0 0 0 0 1 0
shift by 2:   0 0 0 0 0 1 0 0
shift by 3:   0 0 0 0 1 0 0 0
shift by 4:   0 0 0 1 0 0 0 0

Получив это, мы можем применить маску к карте и посмотреть, установлено ли значение:

map:             1 0 0 1 1 1 0 1
mask:            0 0 0 1 0 0 0 0
                 ---------------
result of AND:   0 0 0 1 0 0 0 0

Поскольку результат равен! = 0, мы можем сказать, что индекс 4 включен в карту.

Answer 2

Я думаю, вам нужно что-то вроде этого:

public boolean equalsTarget( int bitmap, int [] numbers, int target ) {
  int sum = 0; // this is the variable we're storing the running sum of our numbers
  int mask = 1; // this is the bitmask that we're using to query the bitmap
  for( int i = 0; i < numbers.length; i++ ) { // for each number in our array
    if( bitmap & mask > 0 ) { // test if the ith bit is 1
        sum += numbers[ i ]; // and add the ith number to the sum if it is
    } 
    mask <<= 1; // shift the mask bit left by 1
  }
  return sum == target; //if the sum equals the target, this bitmap is a match
}

Остальная часть вашего кода довольно проста: вы просто вводите все возможные значения вашего растрового изображения (1..65535) в этот метод и воздействуете на результат.

P.s .: Пожалуйста, убедитесь, что вы полностью понимаете решение, а не просто копируете его, иначе вы просто обманываете себя. :)

Pps: использование int в этом случае работает, так как int имеет ширину 32 бита, и нам нужно только 16. Будьте осторожны с побитовыми операциями, хотя, если вам нужны все биты, как и все примитивные целочисленные типы (байты, короткие , int, long) подписаны на Java.

Answer 3

ОК, поэтому вам разрешен один массив.Предположительно, этот массив содержит первый набор данных.Таким образом, ваш подход не должен иметь никаких дополнительных массивов.

В этом случае битовый вектор - это просто ментальная конструкция модели.Идея такова: если вы попробуете любую возможную комбинацию (примечание, НЕ перестановку), то вы найдете ближайшую сумму к вашей цели.Допустим, у вас есть N номеров.Это означает, что у вас есть 2^N возможных комбинаций.

Бит-векторный подход состоит в том, чтобы нумеровать каждую комбинацию с 0 до 2^N - 1 и пробовать каждую.

Предполагая, что у вас меньшечто 32 числа в массиве, у вас по существу есть внешний цикл, подобный этому:

int numberOfCombinations = (1 << numbers.length - 1) - 1;
for (int i = 0; i < numberOfCombinations; ++i) { ... }

для каждого значения i, вам нужно перейти на каждое число в numbers, решив добавить или пропуститьна основе сдвигов и битовых масок i.

Answer 4

Таким образом, задача состоит в том, чтобы алгоритм, который, учитывая набор A неотрицательных чисел и целевое значение k, определяет, существует ли подмножество A, такое, что сумма его элементов равна k.

Я бы подошел к этому, используя индукцию по A, отслеживая, какие числа <= k являются суммами подмножества набора элементов, обработанных до сих пор. То есть: </p>

boolean[] reachable = new boolean[k+1];
reachable[0] = true;
for (int a : A) {
    // compute the new reachable
    // hint: what's the relationship between subsets of S and S \/ {a} ?
}
return reachable[k];

Битовая карта - это, с математической точки зрения, функция, отображающая диапазон чисел на {0, 1}. A boolean[] отображает индексы массива на логические значения. Таким образом, можно назвать boolean[] растровым изображением.

Одним из недостатков использования boolean[] является то, что вы должны обрабатывать каждый элемент массива отдельно. Вместо этого можно использовать этот тип long, содержащий 64 бита, и использовать операции сдвига и маскирования для одновременной обработки 64 элементов массива. Но такого рода микрооптимизация подвержена ошибкам и довольно сложна, поэтому обычно не делается в коде, который должен быть надежным и обслуживаемым.

Answer 5

Чтобы сгенерировать все возможные битовые комбинации внутри целого и, следовательно, все возможные подмножества, определенные этой битовой картой, вам просто потребуется, чтобы ваш int начинался с 1 и продолжал увеличивать его до максимально возможного значения, которое может содержать беззнаковое короткое int (все 1 с).В конце каждого внутреннего цикла сравните сумму с целью.Если оно совпадает, у вас есть подмножество решений - распечатайте его.Если нет, попробуйте следующее подмножество.Может кто-нибудь помочь объяснить, как это сделать?Я понимаю концепцию, но не знаю, как ее реализовать.