多项有界背包算法-Java 学习之路

我有一个项目列表，每个项目都有一个价格 - 或者在背包问题方面，一个权重 . 可购买物品的数量仅受预算限制，因此只要消耗的总量不超过某个常数，就可以购买尽可能多的物品 . 我还有一个算法，根据某些变量，告诉每个项目的盈利程度（即每个项目的 Value ） . 所以基本上我有一个有限的背包问题，额外的条件是每个项目不止一个适合背包 .

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

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(budget(size of item list ))* ，记忆 O(budget) . 我还假设一切都适合int .

回复于 2024-04-19T23:50:05+08:00

多项有界背包算法

1 回答

相关问题