POJ 1014 Dividing(多重背包+二进制优化)
2024-08-30 23:15:44
http://poj.org/problem?id=1014
题意:
6个物品,每个物品都有其价值和数量,判断是否能价值平分。
思路:
多重背包。利用二进制来转化成0-1背包求解。
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn = ;
int sum;
int a[];
int d[maxn];
int w[maxn]; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int kase = ;
while (scanf("%d", &a[]))
{
for (int i = ; i <= ; i++)
scanf("%d", &a[i]);
sum = ;
for (int i = ; i <= ; i++)
sum += i*a[i];
if (sum == ) break; printf("Collection #%d:\n", ++kase); if (sum % )
{
printf("Can't be divided.\n\n");
continue;
}
int count = ;
for (int i = ; i <= ; i++)
{
int m = a[i];
int k = ;
while (k < m)
{
w[count++] = k*i;
m -= k;
k *= ;
}
w[count++] = m*i;
}
sum = sum / ;
memset(d, , sizeof(d));
for (int i = ; i < count; i++)
{
for (int j = sum; j >= w[i]; j--)
d[j] = max(d[j], d[j - w[i]] + w[i]);
}
if (d[sum]==sum)
printf("Can be divided.\n\n");
else
printf("Can't be divided.\n\n");
}
}
最新文章
- CSS 选择器
- Android日志猫的使用
- 激!QTREE系列
- ElasticSearch实战-入门
- 大师教你<;部落冲突>;如何切换账号
- Uva 12563,劲歌金曲,01背包
- NFC手机
- freepbx 安装和配置
- git add --all 为啥不能添加空文件夹,这样设计的初衷是
- 剑指offer 调整数组顺序使得奇数位于偶数前面
- 一次php涉及跨域功能的麻烦及解决方案
- J2EE Exception:WELD-001408 Unsatisfied dependencies for type [SelectModelFactory] with qualifiers [@
- Codeforces 607A - Chain Reaction - [DP+二分]
- 【xsy2303】呀 dp
- HTTP Status 500 PWC6188 jsp/jstl/core cannot be resolved in either web.xml or the jar files deployed with this application
- Android学习之——单击ActionBar实现ListView返回顶部
- 2018.10.15 loj#6013. 「网络流 24 题」负载平衡(费用流)
- Asp.net Core相关教程及开源项目推荐
- spring4-3-AOP-AspectJ注解-01-简单使用
- STL容器分析--vector
热门文章
- 使用springBoot进行快速开发
- ThinkPHP如果表名有下划线需要用Model应该怎么做?
- 线段树(成段更新,区间求和lazy操作 )
- 我的天$删除注册表$安装mysql最后一步不能启动服务的解决办法
- apache+tomcat实现session共享
- sort命令详解及Nginx统计运用
- 使用angular路由切换后 轮播以及iscrollJs失效的问题
- 洛谷P2444 病毒【AC自动机】
- Codeforces Round #434 (Div. 2, based on Technocup 2018 Elimination Round 1)
- Python自动发布Image service的实现