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

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

給你以下三個輸入：

    baseCosts ，一個長度為 n 的整數(shù)數(shù)組，其中每個 baseCosts[i] 表示第 i 種冰激凌基料的價格。
    toppingCosts，一個長度為 m 的整數(shù)數(shù)組，其中每個 toppingCosts[i] 表示 一份 第 i 種冰激凌配料的價格。
    target ，一個整數(shù)，表示你制作甜點的目標價格。

你希望自己做的甜點總成本盡可能接近目標價格 target 。

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

 

示例 1：

輸入：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 。

示例 2：

輸入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
輸出：17
解釋：考慮下面的方案組合（所有下標均從 0 開始）：
- 選擇 1 號基料：成本 3
- 選擇 1 份 0 號配料：成本 1 x 4 = 4
- 選擇 2 份 1 號配料：成本 2 x 5 = 10
- 選擇 0 份 2 號配料：成本 0 x 100 = 0
總成本：3 + 4 + 10 + 0 = 17 。不存在總成本為 18 的甜點制作方案。

示例 3：

輸入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
輸出：8
解釋：可以制作總成本為 8 和 10 的甜點。返回 8 ，因為這是成本更低的方案。

解法一：搜索

枚舉所有能選的基料，選定一種基料后，搜索所有配料的可能性，每種配料有三種選擇： [ 選 1 個 ， 選 2 個 ， 不 選 ] [選1個，選2個，不選] [選1個，選2個，不選]，保存最優(yōu)的結(jié)果即可。

創(chuàng)新互聯(lián)服務(wù)項目包括從江網(wǎng)站建設(shè)、從江網(wǎng)站制作、從江網(wǎng)頁制作以及從江網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，從江網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到從江省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

• 時間復(fù)雜度： O ( n 3 m ) O(n3^{m}) O(n3m), 每個位置3種狀態(tài)。
• 空間復(fù)雜度： O ( 1 ) O(1) O(1)， 忽略遞歸產(chǎn)生的空間。

class Solution {int ans = 0x3f3f3f3f; 
    public int closestCost(int[] base, int[] top, int target) {for (int x : base) dfs(0, x, target, top);
        return ans;
    }
    void dfs(int x, int sum , int target, int[] top) {int a = Math.abs(target - sum), b = Math.abs(target - ans);
        if (a< b) ans = sum;
        if (a == b && sum< ans) ans = sum; 
        if (sum >target) return;
        for (int i = x; i< top.length; i++) {dfs(i + 1, sum + top[i], target, top);
            dfs(i + 1, sum + 2 * top[i], target, top);
        }
    }
}

class Solution {public:
    int ans = 0x3f3f3f3f; 
    int closestCost(vector& base, vector& top, int target) {for (int x : base) dfs(0, x, target, top);
        return ans;
    }
    void dfs(int x, int sum , int target, vector& top) {int a = abs(target - sum), b = abs(target - ans);
        if (a< b) ans = sum;
        if (a == b && sum< ans) ans = sum; 
        if (sum >target) return;
        for (int i = x; i< top.size(); i++) {dfs(i + 1, sum + top[i], target, top);
            dfs(i + 1, sum + 2 * top[i], target, top);
        }
    } 
};

解法二：動態(tài)規(guī)劃

使用01背包去判斷某個體積V是否能夠被拼湊，取得與target差距最小且成本最小的一個即可。

對于每個基料必須選一個，那么對于大于target的基料就直接判斷就可以了，如過小于target，那么就作為dp數(shù)組的初始狀態(tài)。

在計算狀態(tài)時，還要判斷一下超過target的值是否是最優(yōu)答案，最后再遍歷一次dp數(shù)組，統(tǒng)計小于等于target中是否有最優(yōu)的答案。

• 時間復(fù)雜度： O ( m ? t a r g e t ) O(m*target) O(m?target)
• 空間復(fù)雜度： O ( t a r g e t ) O(target) O(target)

class Solution {public int closestCost(int[] base, int[] top, int V) {boolean[] dp = new boolean[V + 5];
        int ans = Integer.MAX_VALUE;
        for (int x : base) {//判斷只能選基料
            if (x >V) ans = Math.min(ans, x);
            else dp[x] = true;
        }
        for (int x : top) {for (int i = 0; i< 2; i++) {//選2次
                for (int j = V; j >= 0; j--) {if (dp[j] && j + x >V) ans = Math.min(ans, j + x); //計算大于的情況
                    if (j >x) dp[j] |= dp[j - x];
                }
            }
        }
        //ans-V:目前獲得與target的差距 
        for (int i = 0; i<= ans - V && i<= V; i++) if (dp[V - i]) return V - i;
        return ans;
    }
}

---

如果有問題,歡迎評論區(qū)交流, 如果有幫助到你，請給題解點個贊和收藏哈~~~

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁題目：Leetcode1774.最接近目標價格的甜點成本-創(chuàng)新互聯(lián)
URL地址：http://www.chinadenli.net/article40/dcseho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、域名注冊、企業(yè)建站、品牌網(wǎng)站建設(shè)、全網(wǎng)營銷推廣、用戶體驗

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)