捡苹果(贪心和完全背包 动态规划)

• 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;
}