P1757 通天之分组背包
2024-08-25 21:45:11
P1757 通天之分组背包
背包中的经典问题,我竟然不知道。
分组背包
就是每个物品有一个所属的小组,小组内的物品会冲突。
就是把01背包中的两个for换一下位置
01:
for(i,1,kind)
for(j,v,w[i])
分组背包
for(j,v,w[i])
for(i,1,kind)
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
#define inf 2147483647
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()
//by war
//2017.10.17
using namespace std;
int n,m,x,y,z;
struct bag
{
int cnt;
int v[];
int w[];
}a[];
int f[];
bool b[];
int kind;
int ans;
void in(int &x)
{
int y=;
char c=g();x=;
while(c<''||c>'')
{
if(c=='-')
y=-;
c=g();
}
while(c<=''&&c>='')x=x*+c-'',c=g();
x*=y;
}
void o(int x)
{
if(x<)
{
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
}
int main()
{
in(m),in(n);
For(i,,n)
{
in(x),in(y),in(z);
if(!b[z])
{
kind++;
b[z]=true;
}
a[z].cnt++;
a[z].v[a[z].cnt]=y;
a[z].w[a[z].cnt]=x;
}
For(i,,kind)
{
for(int t=m;t>=;t--)
For(j,,a[i].cnt)
if(t>=a[i].w[j])
f[t]=max(f[t],f[t-a[i].w[j]]+a[i].v[j]);
}
o(f[m]);
return ;
}
最新文章
- Android知识点总结[转]
- hdu5452 Minimum Cut
- iOS 二维数组排序小算法
- ExtJs Column 显示文字内容过长 使用Tootip显示全部内容
- 跨过slf4j和logback,直接晋级log4j 2
- 浅谈SqlCommand
- 在C51中如何实现软复位?
- Ajax请求ashx返回各类数据的常见处理方式
- cmd dos 下 无法显示中文
- 支付平台程序,支付程序,网络pos程序,api接口程序,锋锐支付平台程序开发领导者!
- 多元线性相关Matlab代码
- adb not responding. if you&#39;d like to
- drf序列化组件
- Linux本地yum源配置以及使用yum源安装gcc编译环境
- Go基础系列:接口类型断言和type-switch
- Android应用系列:双击返回键退出程序
- Numbers
- Facebook Login api
- Recover Binary Search Tree,恢复二叉排序树
- 阿里云服务器内部dns可能出错
热门文章
- linux运维之分析日志相关命令(1)
- 2019.3.12考试&;2019.3.13考试&;ESTR
- C++并发编程实战---阅读笔记
- 《剑指offer》— JavaScript(26)二叉搜索树与双向链表
- Andrew Ng机器学习课程,第一周作业,python版本
- webService与分布式与微服务与SOA的关系
- 【hihocoder】二分&#183;归并排序之逆序对
- docker mysql authentication_string client does not support authentication 连接问题
- Spring RedisTemplate操作-HyperLogLog操作(7)
- spring框架学习(一)入门