使用动态变量优化背包 [英] knapsack optimization with dynamic variables

问题描述

我正在尝试解决一个优化问题，它与背包问题非常相似，但无法使用动态规划解决.我要解决的问题和这个问题很相似:

I am trying to solve an optimization problem, that it's very similar to the knapsack problem but it can not be solved using the dynamic programming. The problem I want to solve is very similar to this problem:

推荐答案

您确实可以使用 CPLEX 解决此问题.让我在 OPL 中向您展示这一点.

indeed you may solve this with CPLEX. Let me show you that in OPL.

模型(.mod)

{string} categories=...;

{string} groups[categories]=...;

{string} allGroups=union (c in categories) groups[c];

{string} products[allGroups]=...;
{string} allProducts=union (g in allGroups) products[g];

float prices[allProducts]=...;

int Uc[categories]=...;
float Ug[allGroups]=...;

float budget=...;

dvar boolean z[allProducts]; // product out or in ?

dexpr int xg[g in allGroups]=(1<=sum(p in products[g]) z[p]);
dexpr int xc[c in categories]=(1<=sum(g in groups[c]) xg[g]);

maximize 
sum(c in categories) Uc[c]*xc[c]+
sum(c in categories) sum(g in groups[c]) Uc[c]*Ug[g]*xg[g];
subject to
{
ctBudget:
    sum(p in allProducts) z[p]*prices[p]<=budget;
}

{string} solution={p | p in allProducts : z[p]==1};

execute
{
writeln("solution = ",solution);
}

数据 .dat

categories={Carbs,Protein,Fat};
groups=[{Meat,Milk},{Pasta,Bread},{Oil,Butter}];
products=[
{Product11,Product12},{Product21,Product22,Product23},
{Product31,Product32},{Product41,Product42},
{Product51},{Product61,Product62}];

prices=[1,4,1,3,2,4,2,1,3,1,2,1];

// User 1
Uc=[1,1,0];
Ug=[0.8,0.2,0.1,1,0.01,0.6];
budget=3;

//User 2
//Uc=[1,1,0];
//Ug=[0.8,0.2,0.1,1,0.01,0.6];
//budget=2;

这给了

solution =  {"Product11" "Product21" "Product41"}

这篇关于使用动态变量优化背包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！