-> 규정 준수 가이드 기본 설명 3 – 혼합 백팩(가방 템플릿)

01배낭, 완전배낭, 다중완전배낭 문제를 결합하면 3가지 배낭을 혼합하는 문제입니다.
세 가지 배낭의 사상에 따라 세 가지 배낭을 혼합한 문제를 이렇게 풀 수 있다. for(int i=1;i<=N;++i)if(첫 번째 아이템은 01배낭)zeroOnePack(c[i], w[i]).else if(i 번째 아이템은 완전 가방)completePack(c[i], w[i]);else if(첫 번째 아이템은 다중 완전 가방)multiplePack(c[i], w[i], n[i]);이렇게 해서 가장 좋은 결과를 얻을 수 있는 이유는 앞의 층이 이미 가장 좋은 결과를 얻었기 때문이다. 현재 층이 가장 좋은 결과를 구할 때 우리는 세 가지 배낭 중 어떤 방법을 사용해야 하는지 생각하지 않고 앞의 층이 어떻게 가장 좋은 결과를 얻었는지 고려하지 않는다.

#include 
#include <string.h>
int cash;
int n[11],dk[11];
int dp[1000000];
inline int max(const int &a, const int &b)
{
    return a < b ? b : a;
}
void CompletePack(int cost)
{
    for(int i=cost; i<=cash; ++i)
        dp[i] = max(dp[i],dp[i-cost]+cost);
}
void ZeroOnePack(int cost)
{
    for(int i=cash; i>=cost; --i)
        dp[i] = max(dp[i],dp[i-cost]+cost);
}
void MultiplePack(int cnt, int cost)
{
    if(cnt*cost >=cash)//   i              ，          
        CompletePack(cost);
    else
    {
        int k = 1;//     
        while(k//              k
        {
            ZeroOnePack(cost*k);
            cnt -=k;
            k<<=1;
        }
        ZeroOnePack(cnt*cost);
    }
}
int main()
{
    //            
    return 0;
}

만약 당신에게 도움이 된다면 호평하는 것을 잊지 마세요.모모다!!다음에 또 만나요!88
전재 대상:https://www.cnblogs.com/cangT-Tlan/p/6217401.html