algorithm - 多项目有界背包算法

Question

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

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

Answer 1

设 dp[i] 是我们的预算为 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(预算)。我也假设了一切适合 int。