撿蘋果(貪心和完全背包 動態規劃)

• 2020 年 11 月 21 日
• 筆記
• 動態規劃, 算法, 算法分析與設計, 貪心

Description

以前，有個神秘的院子裏面有三種蘋果，每個蘋果的數量是無限的。有一個小姑娘帶了一個大袋子來到院子，她從來沒見過這麼多的蘋果。每種蘋果都有大小以及出售的價格，小姑娘想獲得最大的利潤，但是她不知道怎麼才能做到。於是她來向你尋求幫助，你能告訴她能獲得的最大價值嗎？

Input

第一行一個整數T(T <= 50)，表示測試數據的組數。

每組測試數據有四行組成，前三行每行有兩個整數S和P，分別表示每種蘋果的大小(1 <= S <= 100)和價格(1 <= P <= 10000)

第四行有一個整數V(1 <= V <= 100,000,000)表示小姑娘袋子的大小。

Output

每組測試數據輸出組數和小姑娘能得到的最大的價值。

Sample Input

1
1 1
2 1
3 1
6

Sample Output

Case 1: 6

背包大小10^8太大了，不能直接當完全背包做，因為數組開闢不了那麼大

因為只有三種蘋果，可以先把一部分的當貪心來處理，剩下的用完全背包

蘋果大小最大100，所以大概可以用10倍最大蘋果大小來做分界數

背包大於1000部分的用貪心，小於1000的用完全背包

動態規劃遞推公式：

還有一個比較坑的地方，蘋果最小1，價值最大10000，背包10^8，所以最後輸出的數會超過int

所以使用long long int

c++代碼：

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
typedef long long ll;
 
struct Apple {
    int size;       // 大小
    int price;      // 價值
    float ratio;    // 性價比
};
 
bool cmp(Apple a, Apple b)
{
    return  a.ratio > b.ratio;  // 性價比降序排序
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t, i;
    ll dp[1000], v;     // v背包容量
    Apple apple[3];
    cin >> t;
    for (i = 1; i <= t; ++i) {
        ll ans = 0;
        for (int j = 0; j < 3; ++j) {
            cin >> apple[j].size >> apple[j].price;
            apple[j].ratio = (float)apple[j].price / apple[j].size; // 計算性價比
        }
        sort(apple, apple + 3, cmp);    // 降序排序
        cin >> v;
        if (v >= 1000)  // v >= 1000就用貪心處理, 把v調整到<1000
        {
            ll temp = (v - 1000) / apple[0].size + 1;   // 最少都有一個蘋果
            ans += temp * apple[0].price;
            v -= temp * apple[0].size;          // 減去貪心處理的背包容量
        }
        // fill(dp, dp + 1000, 0);
		memset(dp, 0, sizeof(dp));      // dp數組初始化0
        for (int j = 0; j < 3; ++j)     // 遍歷三種蘋果
            for (int k = apple[j].size; k <= v; ++k)    // 從蘋果大小開始到背包容量
                if (dp[k] < dp[k - apple[j].size] + apple[j].price)
                    dp[k] = dp[k - apple[j].size] + apple[j].price;
        ans += dp[v];
        cout << "Case " << i << ": " << ans << endl;
    }
    return 0;
}

c代碼：

#include <string.h>
#include <stdio.h>

typedef long long ll;

typedef struct
{
    int size;       // 大小
    int price;      // 價值
    float ratio;    // 性價比
}Apple;

int main()
{
    int t, i, j, k, max;
    ll dp[1000], v;
    Apple apple[3];
    Apple temp;
    scanf("%d", &t);
    for (i = 1; i <= t; ++i)
    {
        ll ans = 0;
        for (j = 0; j < 3; ++j)
        {
            scanf("%d%d", &apple[j].size, &apple[j].price);
            apple[j].ratio = (float)apple[j].price / apple[j].size;     //計算性價比
        }
        for (j = 0; j < 3; j++)     // 選擇排序
        {
            max = j;
            for (k = j + 1; k < 3; k++)
                if (apple[max].ratio < apple[k].ratio)
                    max = k;
            temp = apple[j];
            apple[j] = apple[max];
            apple[max] = temp;
        }
        scanf("%d", &v);
        if (v >= 1000)          // 背包容量>=1000的部分用貪心處理
        {
            ll temp = (v - 1000) / apple[0].size + 1;   // 最少都有一個蘋果
            ans += temp * apple[0].price;
            v -= temp * apple[0].size;              // 更新背包容量
        }
        memset(dp, 0, sizeof(dp));                  // dp數組清零
        for (int j = 0; j < 3; ++j)         // 遍歷三個蘋果
            for (int k = apple[j].size; k <= v; ++k)    // 從蘋果大小開始到背包容量
                if (dp[k] < dp[k - apple[j].size] + apple[j].price)
                    dp[k] = dp[k - apple[j].size] + apple[j].price;
        ans += dp[v];
        printf("Case %d: %lld\n", i, ans);
    }
    return 0;
}