hdoj 3732 Ahui Writes Word (多重背包)
2024-09-01 03:58:47
之前在做背包的题目时看到了这道题,一看,大喜,这不是裸裸的01背包吗!! 然后华丽丽的超时,相信很多人也和我一样没有考虑到数据量的大小。
时隔多日,回过头来看这道题,依旧毫无头绪。。。。不过相比之前,我看到了更多细节。
来看题目吧,可能有100000个单词,然后只有1000ms,但看包的大小,有10000,这样只能允许nlog(n)的算法,还有,每个单词的价值和花费都很小(不大于十),如果不考虑单词的不同,只考虑价值和花费只有最多100种东西,但如果把这些按多重背包的方法来计算依旧会超时,很容易想到和之前01背包的时间复杂度是一样的。
还记得多重背包可以转换为01背包吗??我们不妨把这些物品进行打包,把每种物品分别1个、2个、4个…………(2^k)个进行打包,如果不足2^k个则单独打包,然后把每一包看做一件物品,继续使用01背包的方法进行计算,这样我们就把原来O(nc)的时间复杂度降到了O(clogn)。
//hdoj 3732
//2013-08-10-16.53
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std; int dp[10005];
int vc[11][11];
int w[10005];
int v[10005]; int main()
{
int n, c;
char s[100];
while (scanf("%d %d", &n, &c) != EOF)
{
int a, b;
memset(dp, 0, sizeof(dp));
memset(vc, 0 ,sizeof(vc));
for (int i = 1; i <= n; i++)
{
scanf("%s %d %d", &s, &a, &b);
vc[a][b]++;
}
int cnt = 1;
for (int i = 1; i <= 10; i++)
{
for (int j = 1; j <= 10; j++)
{
if (vc[i][j])
{
int tmp = 1;
while (vc[i][j] > tmp)
{
w[cnt] = tmp*j;
v[cnt] = tmp*i;
vc[i][j] -= tmp;
cnt++;
tmp <<= 1;
}
w[cnt] = j*vc[i][j];
v[cnt] = i*vc[i][j];
cnt++;
}
}
}
for (int i = 1; i < cnt; i++)
{
for (int j = c; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
printf("%d\n", dp[c]);
}
return 0;
}
最新文章
- PyCharm2016.2专业版注册码
- 【2016-10-10】【坚持学习】【Day1】【观察者模式】
- Tomcat(JVM)性能监控方法
- 个性二维码开源专题<;替换定位点>;
- [js] 跨域
- Samba 服务使用的端口和协议(是一组TCP UDP协议的组合,主要使用CIFS协议,有一个Java例子)
- 这是从word发的第一篇博客。
- jquery动态刷新局部表单
- 几种JAVA加密算法
- 使用canvas实现擦除效果
- border-image用法详解
- php curl cookie 读写
- Hibernate的实体类中为什么要继承Serializable?
- Weekly Contest 132
- Service Fabric Placement and Load Balancing
- nginx 内置变量大全(转)
- Linux(CentOS 7) 新增或修改 SSH默认端口
- [Java][Web]Response学习
- spark 在yarn执行job时一直抱0.0.0.0:8030错误
- bash数组操作-定义/初始化/赋值…
热门文章
- 【Netty整理01-快速入门】Netty简单使用Demo(已验证)
- Java:synchronized关键字引出的多种锁
- 基于SpringBoot从零构建博客网站 - 开发设置主页标识和修改个人信息功能
- MySQL metalock的一些技巧(写大于读的案例,以及获得锁的顺序)
- 设计模式-抽象工厂模式(AbstractFactory)
- 浅谈c++中的KMP
- Spring Cloud Alibaba | Nacos服务注册与发现
- .NetCore应用多个target framework
- 【Spring容器】项目启动后初始化数据的两种实践方案
- tomcat一键发布