【藍橋練習系統】【多重背包】 算法提高 貪吃的大嘴

問題描述

　　有一隻特别貪吃的大嘴,她很喜歡吃一種小蛋糕,而每一個小蛋糕有一個美味度,而大嘴是很傲嬌的,一定要吃美味度和剛好為m的小蛋糕,而且大嘴還特别懶,她希望通過吃數量最少的小蛋糕達到這個目的.是以她希望你能設計一個程式幫她決定要吃哪些小蛋糕.

輸入格式

　　先輸入一行包含2個整數m、n,表示大嘴需要吃美味度和為m的小蛋糕,而小蛋糕一共有n種,下面輸入n行,每行2個整數,第一個表示該種小蛋糕的美味度,第二個表示蛋糕店中該種小蛋糕的總數

輸出格式

　　輸出一行包含一個整數表示大嘴最少需要吃的小蛋糕數量,若大嘴無法通過吃小蛋糕達到m的美味度和,則輸出"><“.

樣例輸入

10 2

4 1

2 10

樣例輸出

4

樣例輸入

10 2

4 1

7 3

樣例輸出

><

資料規模和約定

m ≤ 20000,小蛋糕總數量≤50.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

// 解題思路：
// 多重背包模闆題
// 即在恰好裝滿m容量時，最少的物品個數
// 将多重背包轉化為01背包，并采用了二進制優化，當然這道題的資料很小不優化也可以輕松通過
// 原理詳解分析可檢視<<背包九講>>

// 快讀
inline void read(int &x)
{
    register int f = 1; x = 0;
    register char c = getchar();
    while(c > '9' || c < '0')
    {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= f;
}

const int maxm = 2e4 + 5;
// 已裝容量為j的最小物品數
int dp[maxm];
// w為各個物品的體積, cnt 為各個物品的數量
int w[55], cnt[55];
int main()
{
    // 讀入資料
    int n, m;
    read(m); read(n);
    for(int i = 1; i <= n; i++)
    {
        read(w[i]); read(cnt[i]);
    }

    // 初始化dp數組初始狀态為不合法的解,因為不能什麼都不裝就剛好裝滿這個容量,且這道題求的是最小數量,則初始化為inf
    // 若求最大則初始化為-inf
    memset(dp, 0x3f, sizeof(dp));
    // 隻有0的狀态是合法解,因為0可以什麼都不裝,即為0
    dp[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        // 容量允許下的最小數量
        int num = min(cnt[i], m / w[i]);
        // 将個數拆分為二進制,則也同時可組合0~num的任何個數,類似倍增
        for(int k = 1; num > 0; k <<= 1)
        {
            // 如果最後已經超出,則将剩餘的數量直接歸為一組即可
            if(k > num) k = num;
            num -= k;
            // 同01背包狀态轉移
            for(int j = m; j >= w[i]; j--)
            {
                dp[j] = min(dp[j], dp[j - k * w[i]] + k);
            }
        }
    }
    // 輸出結果
    if(dp[m] > 100)
    printf("><");
    else
    printf("%d\n", dp[m]);
    return 0;
}
           

原理可以檢視這位部落客的部落格：背包九講——全篇詳細了解與代碼實作