DMOZ中文网站分类目录-免费收录各类优秀网站的中文网站目录.
  • DmozDir.org
DMOZ目录快速登录入口-免费收录各类优秀网站的中文网站目录.由人工编辑,并提供网站分类目录检索及地区分类目录检索,是站长免费推广网站的有力平台!

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

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

  • 已被浏览: 32 次2020年11月21日    来源:  https://www.cnblogs.com/yanhua-tj/p/14017919.html
  • Description以前,有个神秘的院子里面有三种苹果,每个苹果的数量是无限的。有一个小姑娘带了一个大袋子来到院子,她从来没见过这么多的苹果。每种苹果都有大小以及出售的价格,小姑娘想获得最大的利润,但是她不知道怎么才能做到。于是她来向你

    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的用完全背包

    动态规划递推公式:

    \[dp[i] = max(dp[i],\ dp[i - apple[j].size] + apple[j].price) \\ i = apple[j].size\ ->\ v \\ j = 1 -> 3 \]

    还有一个比较坑的地方,苹果最小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;
    }
    

    以上信息来源于网络,如有侵权,请联系站长删除。

    TAG:贪心 背包 苹果 动态

  • 上一篇:API的使用(3)Arrays 类,Math类,三大特性--继承
  • 与“捡苹果(贪心和完全背包 动态规划)”相关的资讯
  • [C#.NET 拾遗补漏]13:动态构建LINQ查询表达式
  • Redis设计与实现一之简单的动态字符串
  • 全面解析RayFire的动态对象与静态对象
  • c# 调用Go 动态库
  • 算法讲解|贪心算法的理解与分析