여러 항목으로 묶인 배낭 알고리즘

Question

각 항목에 가격이 있거나 배낭 문제와 관련하여 가중치가있는 항목의 목록이 있습니다. 구매할 수있는 항목의 수는 예산에 의해서만 제한되므로, 소비 된 총 금액이 특정 상수를 초과하지 않는 한 바람직한 수만큼 구매할 수 있습니다. 또한 특정 변수를 기반으로 각 항목의 수익 (즉, 각 항목의 가치)을 알 수있는 알고리즘을 가지고 있습니다. 그래서 기본적으로 나는 배낭에 각 항목 중 둘 이상이 들어 맞는 여분의 조건으로 배낭이있는 문제를 가지고 있습니다.

나는 이러한 조건에서 수익을 극대화하고 싶습니다. 나는 효율적인 해결책이 없다는 것을 이해하지만 적어도 실현 가능한 해결책이 있습니까?

Answer 1

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에 맞습니다.