多项目有界背包算法

Question

我有一个物品清单，每个物品都有价格 - 或者就背包问题而言，有一个重量。可购买物品的数量仅受预算限制，因此可以根据需要购买尽可能多的物品，只要花费的总金额不超过某个常数即可。我还有一个算法，可以根据某些变量判断每件商品的盈利情况（即每件商品的价值）。所以基本上我有一个有界的背包问题，有一个额外的条件，即每件物品中有不止一件适合背包。

我想在这些条件下实现利润最大化。我知道没有有效的解决方案，但至少有一个可行的解决方案吗？

Answer 1

如果我们的预算是i，让dp[i]是可以赚取的最大利润。 cost[j] 表示 j 项目的成本和 p[j] 从中获得的利润.我假设 cost[] 和 profit[] 已给出。然后下面是c++中的代码。（假设有 n 个项目）。

  int max_profit(int budget )
  {
       if(budget<=0)
         return 0;
       if(dp[budget]!=-1)return dp[budget];
       int ans=0;
       for(int i=0;i<n;i++)
       {
             if(cost[i]<=budget)
               ans=max(ans,profit[i]+max_profit(budget-cost[i]));
       }
       dp[budget]=ans;
       return ans;
  }
  memset(dp,-1,sizeof(dp));
  cout<< max_profit(budget);

时间复杂度为 O(预算*(项目列表的大小))，内存 O(预算)。我也假设了一切适合整数。

多项目有界背包算法

Multiple-item bounded Knapsack algorithm

algorithm

knapsack-problem