Return Оптимальный набор предметов, которые нужно положить в рюкзак JAVA
Сейчас работаю над задачей о рюкзаке, чтобы вернуть набор оптимальных решений.
это мой метод для этого:
public static int knapsackArray(int val[], int wt[], int W) {
//Get the total number of items.
int N = wt.length;
//Create a matrix.
int[][] V = new int[N + 1][W + 1];
//all columns at row 0 to be 0
for (int col = 0; col <= W; col++) {
V[0][col] = 0;
}
//Fill the first row with 0
for (int row = 0; row <= N; row++) {
V[row][0] = 0;
}
for (int item=1;item<=N;item++){
for (int weight=1;weight<=W;weight++){
if (wt[item-1]<=weight){
V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
}
else {
V[item][weight]=V[item-1][weight];
}
}
}
//Printing the matrix
for (int[] rows : V) {
for (int col : rows) {
System.out.format("%5d", col);
}
System.out.println();
}
return V[N][W];
}
и у меня есть другой метод, который принимает в качестве аргументов набор элементов и бюджет и возвращает набор оптимальных решений для этой проблемы:
public static Set<Item> knapsack(Set<Item> items, int budget) {
//create array of wieghts
int[] weights = new int[items.size()];
//create array of values
int[] values = new int[items.size()];
int i = 0;
for (Item x : items){
weights[i] = x.getWeight();
values[i] = x.getValue();
//System.out.println(x);
i++;
}
/*int N = weights.length;
int[][] V = new int[N + 1][budget + 1];*/
int j = knapsackArray(values, weights, budget);
System.out.println(j);
return null;
}
мой вопрос, как я могу превратить эту матрицу в набор оптимальных элементов. это - мой подход - даже хороший способ решить эту проблему?
Ответы 1
В дополнение к матрице значений, которую вы создаете, внутри knapsackArray вы можете создать вторую матрицу, чтобы отслеживать, как вы дошли до этой точки. (т.е. последний элемент, который вы взяли) Таким образом, когда вы закончите работу с вашим решением DP, вы сможете отследить все элементы, которые вы получили на своем пути. Кроме того, чтобы иметь возможность передать значение обратно в knapsack, вам необходимо передать установленный параметр в knapsackArray.
Ниже приводится грубая демонстрация описанного мною метода.
public static int knapsackArray(int val[], int wt[], int W, Set<int> itemIndices) {
// ...
// Create a matrix.
int[][] V = new int[N + 1][W + 1];
int[][] G = new int[N + 1][W + 1];
// ...
for (int item=1;item<=N;item++) {
for (int weight=1;weight<=W;weight++) {
if (wt[item-1]<=weight) {
int candidate = val[item-1] + V[item-1][weight-wt[item-1]];
if (candidate > V[item-1][weight]) {
V[item][weight] = candidate;
G[item][weight] = item - 1;
}
else {
V[item][weight] = V[item-1][weight];
G[item][weight] = -1;
}
}
else {
V[item][weight]=V[item-1][weight];
G[item][weight] = -1;
}
}
}
int currentItem = N;
int currentWeight = W;
while(currentItem >= 1) {
if (G[currentItem][currentWeight] >= 0) {
itemIndices.add(currentItem - 1);
currentWeight = currentWeight - wt[currentItem - 1];
currentItem = G[currentItem][currentWeight] + 1;
}
else {
currentItem = currentItem - 1;
}
}
// ...
return V[N][W];
}
Как только вы это сделаете, вы можете фактически обработать индексы в этом параметре Set<int> itemIndices и заполнить Set<Item> items методом knapsack, как показано ниже.
public static Set<Item> knapsack(Set<Item> items, int budget) {
// ...
Set<Item> itemsToAdd;
Set<int> itemIndices;
int j = knapsackArray(values, weights, budget, itemIndices);
int i = 0;
for (Item x : items) {
if (itemIndices.contains(i)) {
itemsToAdd.add(x);
}
i++;
}
return itemsToAdd;
}
Простите. Это была опечатка
Умм ... Я попробую отладить / обновить свой код, если вы можете предоставить пример ввода и вывода в своем вопросе.
некоторые тесты: `@Test public void testTwoItemsOneFits () {Set <Item> items = buildSet (new Item (2, 20), new Item (10, 2)); assertEquals (buildSet (новый элемент (2, 20)), Solution.knapsack (items, 2)); } `
@Test public void testNoItems() { assertEquals(buildSet(), Solution.knapsack(buildSet(), 42)); } @Test public void testOneItemFits() { Set<Item> items = buildSet(new Item(10, 20)); assertEquals(new HashSet<>(items), Solution.knapsack(items, 15)); }Я получаю ArrayIndexOutOfBoundsException для последних 2!
извините, что плохо, у меня было несколько опечаток, но это все еще не удается: testTwoItemsOneFits для этого я все еще получаю ArrayIndexOutOfBoundsException
Я вроде как исправил это, но теперь я схожу только с половиной тестов, мой вопрос: почему я должен добавлять элементы после того, как я сделал itemIndices?
С моей стороны это была ошибка наименования. Для добавления экземпляров Item следует использовать отдельный набор, а не параметр items в функции knapsack. Я соответствующим образом обновил свой код.
спасибо, но у меня есть один вопрос: «while (item> = 1)», каково значение элемента, поскольку он находится вне цикла for, чем его следует инициализировать?