Поиск идентификатора предмета в задании на рюкзак 0-1 java - PullRequest
Новая
       63

Поиск идентификатора предмета в задании на рюкзак 0-1 java

0 голосов
/ 01 мая 2020

Я нашел решение динамического программирования для задачи «Рюкзак», и, похоже, все в порядке, хотя я намерен не только найти наибольшее значение Предметов, но и пометить эти Предметы и, наконец, собрать их в Список: 

public class DynamicCalculator {
    private Knapsack knapsack = new Knapsack();
    private Item[] availableItems;
    private int[] values;
    private int[] weights;
    List<Item>resItems =new ArrayList <>(  );

    public void initialise() {

        try(BufferedReader reader = Input.getReader()) {
            System.out.println( "Enter the capacity of the knapsack:" );
            int capacityOfKnapsack = Integer.parseInt( reader.readLine() );
            knapsack.setCapacity( capacityOfKnapsack );
            System.out.println( "Enter the number of available thing:" );
            int numberOfThings = Integer.parseInt( reader.readLine() );
            availableItems = new Item[ numberOfThings ];
            values =  new int[ numberOfThings ];
            weights =  new int[ numberOfThings ];
                for (int i = 0; i < numberOfThings; i++) {
                    System.out.println( "Enter the weight of thing " + i );
                    int weight = Integer.parseInt( reader.readLine() );
                    weights[ i ] = weight;
                    System.out.println( "Enter the value of thing " + i );
                    int value = Integer.parseInt( reader.readLine() );
                    values[ i ] = value;
                Item item = new Item( i, weight, value );
                availableItems[ i ] = item;

            }
        } catch (IOException e) {
            e.printStackTrace();
        }

    }

    public void fillKnacksackAndPrint(){
        int maximisedValue = knapsackDP( weights, values, availableItems.length, knapsack.getCapacity() );
        System.out.println("result: "+maximisedValue);
    }
    public int knapsackDP ( int[] totalWeights, int[] totalValues, int itemNum, int maxWeight){
            if (itemNum <= 0 || maxWeight <= 0) {
                return 0;
            }

            int[][] matrix = new int[ itemNum + 1 ][ maxWeight + 1 ];
            for (int j = 0; j <= maxWeight; j++) {
                matrix[ 0 ][ j ] = 0;
            }

            for (int i = 1; i <= itemNum; i++) {
                for (int j = 1; j <= maxWeight; j++) {
                    if (totalWeights[ i - 1 ] > j) {
                        matrix[ i ][ j ] = matrix[ i - 1 ][ j ];
/*
                      Here is gonna be some logic of storing Items like:   resItems.add(  )..
*/
                    } else {
                        matrix[ i ][ j ] = Math.max(
                                matrix[ i - 1 ][ j ],
                                matrix[ i - 1 ][ j - totalWeights[ i - 1 ] ] + totalValues[ i - 1 ] );
                    }
                }
            }
            return matrix[ itemNum ][ maxWeight ];
        }

}

Так что resultList должен собрать все достойные предметы, но я не знаю, как прочитать все промежуточные пики. 2-мерный массив просто перезаписывает пузырь, но я не могу сохранить результат как объект. Любые идеи? Или я не был достаточно терпелив, и где-то существует общее решение?

...