Multiple-item bounded Knapsack algorithm

Question

I have a list of items that each have a price - or in terms of the Knapsack problem, a weight. The number of purchasable items are only limited by a budget, so it is possible to buy as many of each as desirable, as long as the total amount spent isn't over a certain constant. I also have an algorithm that, based on certain variables, tells how profitable each item is (i.e. the value of each item). So basically I have a bounded Knapsack problem with the extra condition that more than one of each item fits into the knapsack.

I want to maximize the profit under these conditions. I understand that there isn't an efficient solution, but is there at least a feasible one?

Is a solution that has the same complexity as a standard knapsack feasible? — kraskevich
a dp array of size budget will be needed, complexity will be O(budget*(size of item list)) — sashas

sashas sashas · Accepted Answer · 2015-01-02T17:05:43

Let dp[i] be the maximum profit that can be earned if our budget is i. And cost[j] denote cost of j item and p[j] the profit earned from it. I assume cost[] and profit[] are given. Then following is the code in c++. ( let there be n items ).

  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);

Time Complexity is O(budget*(size of item list )),Memory O(budget). Also I assumed everything fits in int.

Multiple-item bounded Knapsack algorithm

1 Answers