我正在尝试解决一个优化问题，这个问题与背包问题非常相似，但不能使用动态规划来解决。我要解决的问题与以下问题非常相似：

回答：

实际上，你可以使用CPLEX来解决这个问题。让我用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 1Uc=[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"}