前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU.2111 Saving HDU(贪心)

HDU.2111 Saving HDU(贪心)

作者头像
Enterprise_
发布2019-02-21 17:13:57
4290
发布2019-02-21 17:13:57
举报
文章被收录于专栏:小L的魔法馆小L的魔法馆
  • 题目来源:Saving HDU
  • 题意分析: XHD有个容量为v的口袋,有n个宝贝,每种宝贝的价值不一样,每种宝贝单位体积的价格也不一样,宝贝可以分割,分割后的价值和对应的体积成正比。求XHD最多能取回多少价值的宝贝?
  • 我的思路 一开始我没想明白,认为给的价值是一种宝贝的总价值,所以样例我都解释不了,想到给的价值是单位体积的价值,而不是总价值,就可以解释了,理解题意是很重要的,要不然下不去手啊Orz. 接下来就是贪心了,体积都是一样的,如果想要拿到价值最高的东西,那么每体积的价值都要尽可能高才行,所以策略就是每次取一体积价值最高的宝贝,直到放不下为止。 那么就是按照价值的大小从降序排列,最后输出答案。
  • 完整代码:
代码语言:javascript
复制
#include<stdio.h>
typedef struct
{
    int volume; //该种宝贝的总体积
    int value;  //单位体积的价值,不是总价值
}goods;
int main(void)
{
    int v, n, i, j,ans, t;    //口袋容量卡v,宝贝种类n,总价值ans,累计宝贝的体积t
    goods a[101], temp;
    while (scanf("%d", &v) && v != 0)
    {
        ans = 0, t = 0;
        scanf("%d",&n);            //读入宝贝种类n
        for (i = 0; i < n; i++)
            scanf("%d%d",&a[i].value,&a[i].volume);
        for (i = 0; i < n - 1; i++)
        {
            for (j = 0; j < n - 1 - i; j++)
            {
                if (a[j].value < a[j + 1].value)
                {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        for (i = 0; i < n; i++)
        {
            if (v == t)       
                break;
            for (j = 0; j < a[i].volume; j++)
            {
                if (v == t)
                    break;
                else
                {
                    ans += a[i].value;
                    t++;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年09月01日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档