algorithm - 多项目有界背包算法

我有一个物品清单，每个都有一个价格，或者是背包问题，一个重量。可购买物品的数量只受预算的限制，因此只要花费的总金额不超过某个常数，就有可能购买尽可能多的物品我也有一个算法，基于某些变量，告诉每个项目的盈利情况（即每个项目的价值）。所以基本上我有一个有界背包问题，附加条件是每个背包中有多个物品。
我想在这些条件下最大化利润。我知道没有一个有效的解决办法，但至少有一个可行的办法吗？

最佳答案

如果我们的预算是I，那么DP[i]是可以赚取的最大利润，而成本[J ]表示J项目的成本，而PJ则是从中赚取的利润。我假设成本和利润都是给定的。下面是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（预算）。我也假设了一切
适合内景。

关于algorithm - 多项目有界背包算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27745317/