华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1261|回复: 4
打印 上一主题 下一主题

P1757 通天之分组背包

[复制链接]

738

主题

1485

帖子

5420

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5420
跳转到指定楼层
楼主
发表于 2018-6-29 18:32:42 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
https://www.luogu.org/problemnew/show/P1757

题目背景
直达通天路·小A历险记第二篇

题目描述
自01背包问世之后,小A对此深感兴趣。一天,小A去远游,却发现他的背包不同于01背包,他的物品大致可分为k组,每组中的物品相互冲突,现在,他想知道最大的利用价值是多少。

输入输出格式
输入格式:
两个数m,n,表示一共有n件物品,总重量为m

接下来n行,每行3个数ai,bi,ci,表示物品的重量,利用价值,所属组数

输出格式:
一个数,最大的利用价值

输入输出样例
输入样例#1:
45 3
10 10 1
10 5 1
50 400 2
输出样例#1:
10
说明
1<=m<=1000 1<=n<=1000 组数t<=100
回复

使用道具 举报

0

主题

30

帖子

91

积分

注册会员

Rank: 2

积分
91
沙发
发表于 2018-7-29 08:53:15 | 只看该作者
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. int thing[101][1001],a[1001],b[1001],cnt[101],f[1001];
  5. int main()
  6. {
  7.         int n,m,c,maximum=-999;
  8.         scanf("%d%d",&m,&n);
  9.         for(int i=1;i<=n;i++)
  10.         {
  11.                 scanf("%d%d%d",&a[i],&b[i],&c);
  12.                 thing[c][++cnt[c]]=i;
  13.                 maximum=max(maximum,c);
  14.         }
  15.         for(int k=1;k<=maximum;k++)
  16.                 for(int v=m;v>=0;v--)
  17.                         for(int i=1;i<=cnt[k];i++)
  18.                                 if(v>=a[thing[k][i]])
  19.                                         f[v]=max(f[v],f[v-a[thing[k][i]]]+b[thing[k][i]]);
  20.         printf("%d",f[m]);
  21.         return 0;
  22. }
复制代码
回复 支持 反对

使用道具 举报

9

主题

89

帖子

292

积分

华一学生

积分
292
板凳
发表于 2018-7-29 17:09:22 | 只看该作者
  1. #include<iostream>
  2. using namespace std;
  3. int n,sumv;
  4. const int mx=1010;
  5. int v[mx],w[mx],t[mx];
  6. int dp[mx],i,j,k;
  7. int sumc,c[110][110],countc[110];///sumc总组数
  8. int main()///countc[i]第i组个数
  9. {
  10.     cin>>sumv>>n;
  11.     for (i=1; i<=n; i++)
  12.     {
  13.         cin>>v[i]>>w[i]>>t[i];
  14.         sumc=max(sumc,t[i]);
  15.         countc[t[i]]++;
  16.         c[t[i]][countc[t[i]]]=i;
  17.     }
  18.     for (i=1; i<=sumc; i++)///枚举组数
  19.         for (j=sumv; j>=0; j--)
  20.             for (k=1; k<=countc[i]; k++)
  21.                 if (j>=v[c[i][k]])
  22.                     dp[j]=max(dp[j],dp[j-v[c[i][k]]]+w[c[i][k]]);
  23.     cout<<dp[sumv];
  24.     return 0;
  25. }
复制代码
回复 支持 反对

使用道具 举报

9

主题

89

帖子

292

积分

华一学生

积分
292
地板
发表于 2018-7-29 17:10:00 | 只看该作者
分组背包+跳转表
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-11-2 02:31 , Processed in 0.656204 second(s), 22 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表