Это похоже на рюкзак или алгоритм изменения?

Question

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

Пример 1: - мешок может содержать максимум до 240 кг веса

Item1- 60кг, 30кг Item2-, Item3- 55кг, 60кг Item4-, Item5- 80кг, 40кг Item6- , Item7- 7кг,

Здесь выбранный элемент должен быть Элемент1, Item4, Item5 и Item6 (60 + 60 + 80 + 40 = 240 кг)

Пример 2: - мешок может содержать максимум до 180 кг веса

Item1- 60кг, 30кг Item2-, Item3- 55кг, 30кг Item4-, Item5- 70кг, 48кг Item6-

Здесь выбранный элемент должен быть Элемент1, Item4, Item5 и Item6 (60 + 70 + 48 = 178 кг)

, который находится ближе всего к 180 кг

Вот мой метод шаблон

public List getSelectedItems(List<Presentation> inputList, int knapsackCapacity){ 
List selectItems; 

// optimized algorith which returns selectItems and inputList containing the 
//left out items i.e which are not selected; 

return selectItems; 
} 

Некоторые люди по сети я называю т Простейшая форма Knapsack problem как это не имеет никакого benifit/прибыль, связанную с ним, и некоторые называют это Change-making problem

Независимо от категории он приходит под я не мог получить алгоритм для этого, и, следовательно, не в состоянии сделать программу Java из него. Любая помощь здесь?

Answer 1

Эта проблема может быть решена оптимально в псевдополиномиальном времени (O(nW)) с использованием динамического программирования. То, что вы должны сделать, это изменить немного решения для рюкзаке 0/1, как это:

if w[i] > W 
    m[i,W] = m[i-1,W] 
else if W - m[i-1, W] < W - m[i-1, W - w[i]] + w[i] 
    m[i,W] = m[i-1,W] 
else 
    m[i-1, W - w[i]] + w[i] 

Где W есть предел веса, w является массивом весов элементов. Разница в том, что вам нужно минимизировать разницу между W и результатом, а не максимизировать сумму значений.

Здесь wikipedia раствор с требуемыми изменениями:

// Input: 
// Weights (stored in array w) 
// Number of distinct items (n) 
// Knapsack capacity (W) 
for j from 0 to W do 
    m[0, j] := 0 // Initialize to 0 
end for 
for i from 1 to n do // for every element in the array 
    for j from 0 to W do // for every possible weight 
    if w[i] > j then // if the element's weight is higher than the max 
     m[i, j] := m[i-1, j] // use the solution that excludes the element 
    // else if the diff between the solution that excludes the element and max weight 
    // is smaller than the one that uses it, use the former. 
    else if (j - m[i-1, j]) < (j - m[i-1, j - w[i]] + w[i]) 
     m[i, j] := m[i-1, j] 
    // else use the element's weight in the solution 
    else 
     m[i, j] := m[i-1, j - w[i]] + w[i] 
    end if 

2D-массив m, это таблица мемоизации, в конце алгоритма, m[k, p] имеет лучшее решение для элементов от 0 до k с максимальный вес p.

EDIT: я реализовал и протестировали его в C++, это должно быть легко портировать на Java:

template<typename T> 
long Weight(const T& w, int size, const int W) 
{ 
    vector<vector<int>> m(size+1, vector<int>(W+1, 0)); 

    for(int i = 1; i <= size; ++i) 
    { 
     for(int j = 0; j <= W; ++j) 
     { 
      if(w[i-1] > j) 
      { 
       m[i][j] = m[i-1][j]; 
      } 
      else if((j - m[i-1][j]) < (j - (m[i-1][j - w[i-1]] + w[i-1]))) 
      { 
       m[i][j] = m[i-1][j]; 
      } 
      else 
      { 
       m[i][j] = m[i-1][j - w[i-1]] + w[i-1]; 
      } 
     } 
    } 

    return m[size][W]; 
} 

Answer 2

Мне нравится этот вопрос так просто хочу поделиться мой подход

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 


public class Test { 

    public static void main(String[] args) { 


    List<Presentation> l = new ArrayList<Presentation>(); 
    Presentation p1=new Presentation("one",20); 
    Presentation p2=new Presentation("two",20); 
    Presentation p3=new Presentation("three",20); 
    Presentation p4=new Presentation("four",20); 
    Presentation p5=new Presentation("five",20); 
    Presentation p6=new Presentation("six",20); 
    Presentation p7=new Presentation("seven",20); 
    Presentation p8=new Presentation("eight",20); 
    Presentation p9=new Presentation("nine",20); 
    Presentation p10=new Presentation("ten",90); 
    Presentation p11=new Presentation("eleven",90); 
    l.add(p1); 
    l.add(p2); 
    l.add(p3); 
    l.add(p4); 
    l.add(p5); 
    l.add(p6); 
    l.add(p6); 
    l.add(p7); 
    l.add(p8); 
    l.add(p9); 
    l.add(p10); 
    l.add(p11); 
    System.out.println(getSelectedItems(l,200)); 
    } 

    private static List<String> getSelectedItems(List<Presentation> l, int knapsackCapacity) { 
    int sum=0; 
    int temp=0; 
    PresentationCompare compare=new PresentationCompare(); 
    List<String> s=new ArrayList<String>(); 
    while(sum!=knapsackCapacity && sum<knapsackCapacity && l.size()!=0){ 
     Presentation maxObj=Collections.max(l,compare); 
     temp+=maxObj.getWeight(); 
     if(temp<=knapsackCapacity){ 
     sum=temp; 
     s.add(maxObj.getName()); 
     l.remove(l.indexOf(maxObj)); 
     }else{ 
     l.remove(l.indexOf(maxObj)); 
     temp=sum; 
     } 
    } 
    return s; 
    } 



} 

---

import java.util.Comparator; 


public class PresentationCompare implements Comparator<Presentation> { 

    public int compare(Presentation o1, Presentation o2) { 
    return o1.weight-o2.weight; 
    } 

} 

Answer 3

Я согласен с imreal-анализом. Но это можно решить без каких-либо изменений в решении для ранца. Просто рассмотрите значение весов, таких как вес. Тогда нам не нужно модифицировать программу для ранца. Вот пример:

import java.util.ArrayList; 
import java.util.List; 
public class Knapsack { 

    public static void main(String[] args) { 

     int[] weight = {60, 30, 55, 60, 80, 40, 7}; 
     int[] value = {60, 30, 55, 60, 80, 40, 7}; 
     int targetSum = 31; 

     knapsack(weight, value, targetSum); 

    } 

    public static void knapsack(int[] weight, int[] value, int targetSum) { 

     int[][] weightValMatrix = new int[weight.length + 1][targetSum + 1]; 

     for (int i = 0; i < weight.length; i++) { 
      for (int k = 0; k < targetSum + 1; k++) { 
       weightValMatrix[i][k] = 0; 
      } 

     } 

     for (int i = 1; i < weight.length + 1; i++) { 
      for (int k = 1; k < targetSum + 1; k++) { 
       if (k < weight[i - 1]) { 
        weightValMatrix[i][k] = weightValMatrix[i - 1][k]; 
       } else { 
        int valueInclusiveCurrentWeight = value[i - 1]; 
        if ((k - weight[i - 1]) > 0) { 
         valueInclusiveCurrentWeight = valueInclusiveCurrentWeight 
           + weightValMatrix[i - 1][k - weight[i - 1]]; 
        } 

        int valueExcludingCurrentWeight = weightValMatrix[i - 1][k]; 
        weightValMatrix[i][k] = valueInclusiveCurrentWeight >= valueExcludingCurrentWeight ? valueInclusiveCurrentWeight 
          : valueExcludingCurrentWeight; 

       } 

      } 



     } 



     for (int i = 1; i < weight.length + 1; i++) { 

      for (int k = 1; k < targetSum + 1; k++) { 

       System.out.print(weightValMatrix[i][k]); 

       if(k == targetSum){ 
        System.out.println(""); 
       } 
      } 
     } 


     System.out.println("final value is " + weightValMatrix[weight.length][targetSum]); 

     List<Integer> finallySelectedWeightIndex = new ArrayList<Integer>(); 

     findActualWeightIndex(weightValMatrix, weight.length, targetSum, finallySelectedWeightIndex, weight); 

     for(int index:finallySelectedWeightIndex){ 
      System.out.println("weight is " + weight[index-1] + " value is "+ value[index-1]); 
     } 


    } 


    public static void findActualWeightIndex(int[][] weightValMatrix, int row, int column, 
      List<Integer> finallySelectedWeightIndex, int[] weight) { 

     if(row==0 || column==0){ 
      return; 
     } 

     if(weightValMatrix[row][column]==weightValMatrix[row-1][column]){ 
      findActualWeightIndex(weightValMatrix, row-1, column, finallySelectedWeightIndex, weight); 
     }else{ 
      finallySelectedWeightIndex.add(row); 
      findActualWeightIndex(weightValMatrix, row-1, column - weight[row-1] , finallySelectedWeightIndex, weight); 
     } 
    } 

}