ruby - 背包：如何将项目类型添加到现有解决方案

Question

我一直在使用这种动态编程的变体来解决背包问题：

KnapsackItem = Struct.new(:name, :cost, :value)
KnapsackProblem = Struct.new(:items, :max_cost)


def dynamic_programming_knapsack(problem)
  num_items = problem.items.size
  items = problem.items
  max_cost = problem.max_cost

  cost_matrix = zeros(num_items, max_cost+1)

  num_items.times do |i|
    (max_cost + 1).times do |j|
      if(items[i].cost > j)
        cost_matrix[i][j] = cost_matrix[i-1][j]
      else
        cost_matrix[i][j] = [cost_matrix[i-1][j], items[i].value + cost_matrix[i-1][j-items[i].cost]].max
      end
    end
  end

  cost_matrix
end

def get_used_items(problem, cost_matrix)
  i = cost_matrix.size - 1
  currentCost = cost_matrix[0].size - 1
  marked = Array.new(cost_matrix.size, 0) 

  while(i >= 0 && currentCost >= 0)
    if(i == 0 && cost_matrix[i][currentCost] > 0 ) || (cost_matrix[i][currentCost] != cost_matrix[i-1][currentCost])
      marked[i] = 1
      currentCost -= problem.items[i].cost
    end
    i -= 1
  end
  marked
end

这对于您只需提供名称、成本和价值的上述结构非常有效。可以像下面这样创建项目：

 items = [
      KnapsackItem.new('david lee', 8000, 30) , 
      KnapsackItem.new('kevin love', 12000, 50), 
      KnapsackItem.new('kemba walker', 7300, 10),
      KnapsackItem.new('jrue holiday', 12300, 30),
      KnapsackItem.new('stephen curry', 10300, 80),
      KnapsackItem.new('lebron james', 5300, 90),
      KnapsackItem.new('kevin durant', 2300, 30),
      KnapsackItem.new('russell westbrook', 9300, 30),
      KnapsackItem.new('kevin martin', 8300, 15),
      KnapsackItem.new('steve nash', 4300, 15),
      KnapsackItem.new('kyle lowry', 6300, 20),
      KnapsackItem.new('monta ellis', 8300, 30),
      KnapsackItem.new('dirk nowitzki', 7300, 25),
      KnapsackItem.new('david lee', 9500, 35),
      KnapsackItem.new('klay thompson', 6800, 28)
    ]

  problem = KnapsackProblem.new(items, 65000)

现在，我遇到的问题是我需要为这些玩家中的每一个添加一个位置，并且我必须让背包算法知道它仍然需要在所有玩家中最大化价值，除非有一个新的限制和那个限制是每个玩家都有一个位置，每个位置只能选择一定的次数。有些位置可以选择两次，有些位置可以选择一次。理想情况下，项目会变成这样：

KnapsackItem = Struct.new(:name, :cost, :position, :value)

职位将有如下限制：

PositionLimits = Struct.new(:position, :max)

限制将被实例化，可能如下所示：

limits = [Struct.new('PG', 2), Struct.new('C', 1), Struct.new('SF', 2), Struct.new('PF', 2), Struct.new('Util', 2)]

让这更棘手的是每个玩家都可以处于 Util 位置。如果我们想禁用 Util 位置，我们只需将 2 设置为 0。

我们原来的 items 数组看起来像下面这样：

items = [
          KnapsackItem.new('david lee', 'PF', 8000, 30) , 
          KnapsackItem.new('kevin love', 'C', 12000, 50), 
          KnapsackItem.new('kemba walker', 'PG', 7300, 10),
          ... etc ...
        ]

如何将位置限制添加到背包算法中，以便仍然保留提供的玩家池的最大值？

Answer 1

ruby 中有一些有效的库可以满足您的任务，很明显您正在寻找一些基于约束的优化，ruby 中有一些库是开源的，因此可以免费使用，只需将它们包含在您的项目中即可。您需要做的就是从您的约束中生成线性规划模型目标函数，并且库的优化器将生成满足您所有约束的解决方案，或者如果无法从给定的约束中得出任何结论，则表示不存在解决方案。

ruby 中可用的一些此类库是

• RGLPK
• 欧联
• LP求解

OPL 遵循类似于 IBM CPLEX 的 LP 语法，后者是广泛使用的优化软件，因此您可以获得有关如何使用此建模 LP 的良好参考，此外，这是构建在 RGLPK 之上的。

Answer 2

据我了解，您指定的附加约束如下：

应该有一组元素，其中最多只能在解中选择 k（k = 1 或 2）个元素。应该有多个这样的集合。

我想到了两种方法，但都不够有效。

方法一：

1. 将元素分成位置组。因此，如果有 5 个位置，则每个元素应分配到 5 个组之一。

2. 通过从每个组中选择 1 个（或 2 个）元素并检查总价值和成本来迭代（或重复）所有组合。您可以通过多种方式了解一些组合。例如，在一个组中，如果有两个元素，其中一个以较低的成本提供更多的价值，那么另一个可以从所有解决方案中被拒绝。

方法二：

Mixed Integer Linear Programming Approach.

将问题表述如下：

Maximize summation (ViXi) {i = 1 to N} 
where Vi is value and 
Xi is a 1/0 variable denoting presence/absence of an element from the solution.

Subject to constraints:
summation (ciXi) <= C_MAX {total cost}
And for each group:
summation (Xj) <= 1 (or 2 depending on position)
All Xi = 0 or 1.

然后你必须找到一个求解器来解决上述 MILP。

Answer 3

这个问题类似于约束车辆路径问题。您可以尝试像 Clarke&Wright 的保存算法这样的启发式算法。您还可以尝试使用较少玩家的蛮力算法。

Answer 4

考虑到玩家有五个位置，您的背包问题将是：-

   Knpsk(W,N,PG,C,SF,PF,Util) = max(Knpsk(W-Cost[N],N-1,...)+Value[N],Knpsk(W,N-1,PG,C,SF,PF,Util),Knpsk(W-Cost[N],N-1,PG,C,SF,PF,Util-1)+Value[N])

    if(Pos[N]=="PG") then Knpsk(W-Cost[N],N-1,....) = Knpsk(W-Cost[N],N-1,PG-1,....)

    if(Pos[N]=="C") then Knpsk(W-Cost[N],N-1,....) = Knpsk(W-Cost[N],N-1,PG,C-1....)

    so on...

  PG,C,SF,PF,Util are current position capacities 
  W is current knapsack capacity
  N number of items available

动态编程可以像以前使用 7-D 表一样使用，并且在您的情况下，位置的值很小，它会使算法减慢 16 倍，这对于 np 完全问题非常有用

以下是JAVA中的动态编程解决方案：

public class KnapsackSolver {

    HashMap CostMatrix;
    // Maximum capacities for positions
    int posCapacity[] = {2,1,2,2,2};
    // Total positions 
    String[] positions = {"PG","C","SF","PF","util"}; 
    ArrayList playerSet = new ArrayList<player>();  
    public ArrayList solutionSet;
    public int bestCost;


    class player {

        int value;
        int cost;
        int pos;
        String name;

        public player(int value,int cost,int pos,String name) {
            this.value = value;
            this.cost = cost;
            this.pos = pos;
            this.name = name;
        }

        public String toString() {
            return("'"+name+"'"+", "+value+", "+cost+", "+positions[pos]);
        }

    }

    // Used to add player to list of available players
    void  additem(String name,int cost,int value,String pos) {
        int i;
        for(i=0;i<positions.length;i++) {
            if(pos.equals(positions[i]))
                break;
        }
        playerSet.add(new player(value,cost,i,name));
    }

    // Converts subproblem data to string for hashing
    public String encode(int Capacity,int Totalitems,int[] positions) {
        String Data = Capacity+","+Totalitems;
        for(int i=0;i<positions.length;i++) {
            Data = Data + "," + positions[i];
        }
        return(Data);
    }

    // Check if subproblem is in hash tables
    int isDone(int capacity,int players,int[] positions) {

        String k = encode(capacity,players,positions);

        if(CostMatrix.containsKey(k)) {
            //System.out.println("Key found: "+k+" "+(Integer)CostMatrix.get(k));
            return((Integer)CostMatrix.get(k));
        }

        return(-1);
    }

    // Adds subproblem added hash table
    void addEncode(int capacity,int players,int[] positions,int value) {

        String k = encode(capacity,players,positions);
        CostMatrix.put(k, value);
    }

    boolean checkvalid(int capacity,int players) {

        return(!(capacity<1||players<0));
    }

    // Solve the Knapsack recursively with Hash look up
    int solve(int capacity,int players,int[] posCapacity) {

        // Check if sub problem is valid

        if(checkvalid(capacity,players)) {

            //System.out.println("Processing: "+encode(capacity,players,posCapacity));

            player current = (player)playerSet.get(players);

            int sum1 = 0,sum2 = 0,sum3 = 0;

            int temp = isDone(capacity,players-1,posCapacity);

            // Donot add player

            if(temp>-1) {

                sum1 = temp;
            }
            else sum1 = solve(capacity,players-1,posCapacity);

            //check if current player can be added to knapsack

            if(capacity>=current.cost) {

                posCapacity[posCapacity.length-1]--;

                temp = isDone(capacity-current.cost,players-1,posCapacity);

                posCapacity[posCapacity.length-1]++;

                // Add player to util

                if(posCapacity[posCapacity.length-1]>0) {

                    if(temp>-1) {

                        sum2 = temp+current.value;
                    }
                    else {

                        posCapacity[posCapacity.length-1]--;
                        sum2 = solve(capacity-current.cost,players-1,posCapacity)+current.value;
                        posCapacity[posCapacity.length-1]++;

                    }

                }

                // Add player at its position

                int i = current.pos;

                    if(posCapacity[i]>0) {

                        posCapacity[i]--;
                        temp  = isDone(capacity-current.cost,players-1,posCapacity);
                        posCapacity[i]++;
                        if(temp>-1) {

                            sum3 = temp+current.value;
                        }
                        else {

                            posCapacity[i]--;
                            sum3 = solve(capacity-current.cost,players-1,posCapacity)+current.value;
                            posCapacity[i]++;

                        }
                    }
                }   

            //System.out.println(sum1+ " "+ sum2+ " " + sum3 );


            // Evaluate the maximum of all subproblem   
            int res = Math.max(Math.max(sum1,sum2), sum3);

            //add current solution to Hash table
            addEncode(capacity, players, posCapacity,res);
            //System.out.println("Encoding: "+encode(capacity,players,posCapacity)+" Cost: "+res);

            return(res);


        }
        return(0);
    }

    void getSolution(int capacity,int players,int[] posCapacity) {


        if(players>=0) {
           player curr = (player)playerSet.get(players);
           int bestcost = isDone(capacity,players,posCapacity);
           int sum1 = 0,sum2 = 0,sum3 = 0;
           //System.out.println(encode(capacity,players-1,posCapacity)+" "+bestcost);
           sum1 = isDone(capacity,players-1,posCapacity);
           posCapacity[posCapacity.length-1]--;
           sum2 = isDone(capacity-curr.cost,players-1,posCapacity) + curr.value;
           posCapacity[posCapacity.length-1]++;
           posCapacity[curr.pos]--;        
           sum3 = isDone(capacity-curr.cost,players-1,posCapacity) + curr.value;
           posCapacity[curr.pos]++;

           if(bestcost==0)
               return;

           // Check if player is not added
           if(sum1==bestcost) {
               getSolution(capacity,players-1,posCapacity);
           }
           // Check if player is added to util
           else if(sum2==bestcost) {
               solutionSet.add(curr);
               //System.out.println(positions[posCapacity.length-1]+" added");
               posCapacity[posCapacity.length-1]--;
               getSolution(capacity-curr.cost,players-1,posCapacity);
               posCapacity[posCapacity.length-1]++;

           }
           else {
               solutionSet.add(curr);
               //System.out.println(positions[curr.pos]+" added");
               posCapacity[curr.pos]--;
               getSolution(capacity-curr.cost,players-1,posCapacity);
               posCapacity[curr.pos]++;     


           }   
        }


   }



    void getOptSet(int capacity) {

        CostMatrix = new HashMap<String,Integer>();
        bestCost = solve(capacity,playerSet.size()-1,posCapacity);
        solutionSet = new ArrayList<player>();
        getSolution(capacity, playerSet.size()-1, posCapacity);

    }



    public static void main(String[] args) {

        KnapsackSolver ks = new KnapsackSolver();
        ks.additem("david lee", 8000, 30, "PG"); 
        ks.additem("kevin love", 12000, 50, "C"); 
        ks.additem("kemba walker", 7300, 10, "SF");
        ks.additem("jrue holiday", 12300, 30, "PF");
        ks.additem("stephen curry", 10300, 80, "PG");
        ks.additem("lebron james", 5300, 90, "PG");
        ks.additem("kevin durant", 2300, 30, "C");
        ks.additem("russell westbrook", 9300, 30, "SF");
        ks.additem("kevin martin", 8300, 15, "PF");
        ks.additem("steve nash", 4300, 15, "C");
        ks.additem("kyle lowry", 6300, 20, "PG");
        ks.additem("monta ellis", 8300, 30, "C");
        ks.additem("dirk nowitzki", 7300, 25, "SF");
        ks.additem("david lee", 9500, 35, "PF");
        ks.additem("klay thompson", 6800, 28,"PG");
        //System.out.println("Items added...");
       // System.out.println(ks.playerSet);
        int maxCost = 30000;
        ks.getOptSet(maxCost);
        System.out.println("Best Value: "+ks.bestCost);
        System.out.println("Solution Set: "+ks.solutionSet);
    }




}

注意：如果添加的某些位置的玩家超过了其容量，则添加为 util 的玩家，因为任何位置的玩家都可以添加到 util 中。