这类似于背包还是改变算法？

3 回答

• 3

  使用动态编程可以在伪多项式时间（ O(nW) ）中最佳地解决此问题 . 你需要做的是修改一下Knapsack 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
  

  二维数组 m 是记忆表，在算法结束时， m[k, p] 为0到 k 之间的元素保存最佳解决方案，最大权重为 p .

  编辑：我在 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];
  }
  

  回复于 2024-04-29T17:19:40+08:00
• 0

  我喜欢这个问题所以只想分享我的方法

  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;
    }
  
  }
  

  回复于 2024-04-29T17:19:40+08:00
• 0

  我同意不真实的分析 . 但是这可以通过背包解决方案的任何修改来解决这个问题 . 只需考虑与权重相同的权重值 . 然后我们不必修改背包程序 . 这是一个例子

  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);
          }
      }
  
  }
  

  回复于 2024-04-29T17:19:40+08:00