题目106 背包问题

冷不防 2022-09-24 08:27 185阅读 0赞

![20160728100513695][]

已AC代码：

#include<cstdio>
    #include<algorithm>
    using namespace std;
    struct Things
    {
            int v;
            int w;
    }t[15];
    bool compare(const Things a, const Things b)
    {
        return a.v > b.v;
    }
    int main()
    {
        int n;
        scanf("%d", &n);
        while(n--)
        {
            int s, m, sum=0;
            scanf("%d%d", &s, &m);
            for(int i=0; i<s; i++)
            {
                scanf("%d%d", &t[i].v, &t[i].w);
            }
            sort(t, t+s, compare);
            for(int i=0; i<s; i++)
            {
                   if((t[i].w) <= m)
                   {
                       sum += t[i].v*t[i].w;
                       m -= t[i].w;
                   }
                   else
                   {
                       sum += m * t[i].v;
                       break;
                   }
            }
            printf("%d\n", sum);
        }
        return 0;
    }

[20160728100513695]: /images/20220719/74f17a46c9d2457db250c057e642d17b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关 01背包总结+题目汇总

们先来理解一下01背包问题：有n种物品与承重为m的背包。每种物品只有一件，每个物品都有对应的重量weight\[i\]与价值value\[i\]，求解如何装包使得价值最大...

缺乏、安全感/ 2024年04月18日 19:14/ 0 赞/ 76 阅读

相关 LeetCode背包问题---题目列表

LeetCode背包问题—动态规划提纲： 01背包 [目标和][Link 1]：转化问题以后为0-1背包方案数问题。 [分

今天药忘吃喽~/ 2022年10月05日 00:48/ 0 赞/ 150 阅读

相关题目106 背包问题

![20160728100513695][] 已AC代码： include<cstdio> include<algorithm> using nam

冷不防/ 2022年09月24日 08:27/ 0 赞/ 186 阅读

相关 Codeforces 106 C Buns【多重背包】

今天拉了一场CF，做了一下，略坑啊、、、首先105A题，竟然卡精度，小数点两位卡精度，需要给他加一个1e-6，算是见识了题目：[Codeforces 106 C

刺骨的言语ヽ痛彻心扉/ 2022年08月12日 13:58/ 0 赞/ 26 阅读

相关南阳OJ106-背包问题（贪心算法）

背包问题时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v

﹏ヽ暗。殇╰゛Y/ 2022年08月04日 12:36/ 0 赞/ 200 阅读

相关南阳题目106-背包问题

背包问题时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v

电玩女神/ 2022年07月26日 12:21/ 0 赞/ 211 阅读

相关贪心算法（背包问题）NYOJ-106

贪心算法所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问

朱雀/ 2022年06月05日 10:35/ 0 赞/ 220 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 384 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 316 阅读

相关 nyoj 106 背包问题（dp或贪心都可）

题目106 [题目信息][Link 1] [运行结果][Link 2] [本题排行][Link 3] [讨论区][Link 4] 背包

阳光穿透心脏的1/2处/ 2022年03月28日 03:39/ 0 赞/ 204 阅读