多项有界背包算法

Question

我有一个项目清单，每个项目都有一个价格--或者就背包问题而言，一个重量。可购买物品的数量只受预算的限制，所以只要总花费不超过某个常数，就有可能购买尽可能多的物品。我也有一个算法，它基于某些变量，告诉每一个项目的利润（即每一个项目的价值）。所以基本上，我有一个有界背包问题，额外的条件是每个物品中有一个以上适合背包。

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

Answer 1

如果我们的预算是i的话，让DP[i]是可以赚取的最大利润。成本[j]指j项的成本，P[j]指从中获得的利润。我假设成本[]和利润[]是给定的。下面是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。