ran*_*its 10 ruby algorithm knapsack-problem
我一直在使用这种动态编程变体来解决背包问题:
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 = [
KnapsackItem.new('david lee', 'PF', 8000, 30) ,
KnapsackItem.new('kevin love', 'C', 12000, 50),
KnapsackItem.new('kemba walker', 'PG', 7300, 10),
... etc ...
]
如何将位置限制添加到背包算法中,以便仍然保留所提供的提供的播放器池的最大值？
考虑到球员有五个位置，你的背包问题将是：-
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。