前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >hdoj 3466 Proud Merchants(01背包)

hdoj 3466 Proud Merchants(01背包)

作者头像
xindoo
发布2021-01-22 15:19:44
2510
发布2021-01-22 15:19:44
举报
文章被收录于专栏:XINDOO的专栏

题目链接

这并不是一题裸的01背包,它在简单到01背包上还加了一个限制条件Q,如果没有Q,这完全是一题裸01背包。

对于这个题目,我们只要加上排序对某些物品进行优先处理就好了。

想想我们为什么要排序, 举个简单的例子,如果数据中出现这样到情况 5 9 3、 6 6 5、5 6 3…… 对5 9 3 处理的时候他只能求出dp[9]然后6 6 5只能在dp[9]的基础上继续处理,它要用到dp[6]、dp[7]……,而这些全是零,但这些一直会是0吗?不是在处理5 6 3的时候可以得到这些值,但6 6 5已经被处理了,它再也不会用的这些了,所以怎么得到正确的结果? 如果我们对5 6 3优先处理就不会出现这样到情况了。

要想到只有后面要用的值前面都可以得到,那么才不会出错。设A:5 9 3 B:5 6 3,如果先A后B,则至少需要p1+q2 = 14的容量,如果先B后A,至少需要p2+q1 = 11的容量,那么就是p1+q2 > p2+q1,变形之后就是q1-p1 < q2-p2。所以要针对每个属性的q-p来进行排序。

代码语言:javascript
复制
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int maxn = 505;
using namespace std;

int dp[5005];
struct node
{
    int p, q, v;
}a[maxn];

int cmp(node x, node y)
{
    return x.q - x.p < y.q - y.p;
}
int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) !=EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d %d %d", &a[i].p, &a[i].q, &a[i].v);
        }
        memset(dp, 0, sizeof(dp));
        sort(a, a+n, cmp);
        for (int i = 1; i <= n; i++)
        {
            for (int j = m; j >= a[i].q; j--)
            {
                dp[j] = max(dp[j], dp[j-a[i].p] + a[i].v);
            }
        }
        printf("%d\n",dp[m]);
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2013-04-24,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

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