Как узнать, какой предмет был выбран в задаче о ранце (реализация DP)? - PullRequest
Новая
       32

Как узнать, какой предмет был выбран в задаче о ранце (реализация DP)?

0 голосов
/ 23 июня 2019

Я реализую проблему ранца на основе этого кода, и я хочу знать, какие элементы были окончательно выбраны.

код: 

Knapsack { 


static int max(int a, int b)  { return (a > b) ? a : b; } 


static int knapSack(int W, int wt[], int val[], int n) 
{ 
    int i, w; 
    int K[][] = new int[n + 1][W + 1]; 

    // Build table K[][] in bottom up manner 
    for (i = 0; i<= n; i++) { 
        for (w = 0; w<= W; w++) { 
            if (i == 0 || w == 0) 
                K[i][w] = 0; 
            else if (wt[i - 1]<= w) 
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); 
            else
                K[i][w] = K[i - 1][w]; 
        } 
    } 

    return K[n][W]; 
} 


public static void main(String args[]) 
{ 
    int val[] = new int[] { 60, 100, 120 }; 
    int wt[] = new int[] { 10, 20, 30 }; 
    int W = 50; 
    int n = val.length; 
    System.out.println(knapSack(W, wt, val, n)); 

     } 

  }

Что я хочу сделать, так этонайти, какие элементы были окончательно вставлены в рюкзак, основываясь на том, как они изначально были сохранены в массиве, и сохранить эти результаты в файле в двоичном формате.

Я имею в виду, что здесь у нас есть 3 элемента в этой частикода, и если, например, элемент номер 1 (тот, который имеет значение 60) и элемент номер 3 (тот, который имеет значение 120) были окончательно выбраны, я хотел бы получить строку, которая будет выглядеть так 10,1

1 Ответ

0 голосов
/ 23 июня 2019

Вы можете добавить следующее к своему коду непосредственно перед оператором возврата: 

        int ind = n;
        int weight = W;
        String s = "";
        while (ind > 0) {
            if (K[ind][weight] != K[ind - 1][weight]) {
                s = "1," + s;
                weight -= wt[ind - 1];
            }
            else {
                s = "0," + s;
            }
            ind -= 1;
        }
        s = s.substring(0, s.length() - 1);
        System.out.println(s);

Этот код по существу возвращает назад из окончательного решения, чтобы увидеть, эквивалентен ли максимум с элементами i максимальному с i -1 элементов (которые указывают, использовался ли i-й элемент).

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

0,1,1
220
...