leetcode1774. 最接近目标價格的甜點成本 動态規劃背包解法

題目

你打算做甜點，現在需要購買配料。目前共有 n 種冰激淩基料和 m 種配料可供選購。而制作甜點需要遵循以下幾條規則：

• 必須選擇 一種 冰激淩基料。
• 可以添加 一種或多種 配料，也可以不添加任何配料。
• 每種類型的配料 最多兩份 。

給你以下三個輸入：

• baseCosts ，一個長度為 n 的整數數組，其中每個 baseCosts[i] 表示第 i 種冰激淩基料的價格。
• toppingCosts，一個長度為 m 的整數數組，其中每個 toppingCosts[i] 表示 一份 第 i 種冰激淩配料的價格。
• target ，一個整數，表示你制作甜點的目标價格。 你希望自己做的甜點總成本盡可能接近目标價格 target 。

傳回最接近 target 的甜點成本。如果有多種方案，傳回 成本相對較低 的一種。

題目示例

輸入：

baseCosts = [1,7], toppingCosts = [3,4], target = 10

輸出： 10

解釋：

考慮下面的方案組合（所有下标均從 0 開始）：

• 選擇 1 号基料：成本 7
• 選擇 1 份 0 号配料：成本 1 x 3 = 3

• 選擇 0 份 1 号配料：成本 0 x 4 = 0

  總成本：7 + 3 + 0 = 10 。

解題思路

01背包問題，将target設為背包的大小，初始化一個大小為target的bag[]數組，若是有基底和配料的組合價格curCost小于等于target，則将

bag[curCost]=ture。若是大于target，則繼續加配料，價格也不會繼續接近target，是以直接放棄這種組合。

首先将價格小于target的基底bag[base]=true；然後用配料toppingCost數組開始背包，若是bag[i]=true，則證明可以繼續背包，加配料。

背包過程中如果有價格小于target，則将這個價格的bag設定為ture，若是bag[target]=true,直接傳回target即可。背包過程中維護一個最接近target的ans值用來傳回。

代碼

class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int ans=baseCosts[0];//先初始化ans為一個基底的價格
        vector<bool> bag(target+1,false); //bag[i]=true的意思為有一種搭配的價格等于i；
        for(auto b:baseCosts)   //将ans變為最接近target的基底價格，并将所有小于target的基底背包設為1，證明這個背包可以繼續加料。如果大于target繼續加料，價格也隻會遠離target。
        {
            if(bag[target])return target;
            if(b<=target)bag[b]=true;
            if(abs(b-target)<abs(ans-target))ans=b;
            else if(abs(b-target)==abs(ans-target))ans=min(ans,b);
        }
        for(auto t:toppingCosts)    //背包，基底已經在背包中初始化了，每種基底可以選兩次。
        {
            for(int i=0;i<2;i++)
            {
                for(int j=target;j>=0;j--)
                {
                    if(bag[target])return target;
                    if(bag[j])
                    {
                        int curCost=j+t;
                        if(abs(curCost-target)<abs(ans-target))ans=curCost;
                        else if(abs(curCost-target)==abs(ans-target))ans=min(ans,curCost);
                        if(curCost<=target)bag[curCost]=true;
                    }
                }
            }
        }
        return ans;
    }
};