HDU 2844 二进制优化的多重背包
2024-09-22 10:36:37
Coins
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11596 Accepted Submission(s): 4634
Problem Description
Whuacmers use coins.They have coins of value A1,A2,A3...An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.
Input
The input contains several test cases. The first line of each test case contains two integers n(1 ≤ n ≤ 100),m(m ≤ 100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000). The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
0 0
Sample Output
8
4
Source
题意:有不同面值的 相应数量不同n种硬币 问1~m元的价格有哪些 可以由硬币组成 f[i]==i
题解: 多重背包 二进制优化
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<queue>
#include<stack>
using namespace std;
int n,m;
struct node
{
int a,c;
} N[];
int f[];
int ans;
int value[],size[];
int count;
void slove(int q)
{
count=;
for(int i=;i<=q;i++)
{
int c=N[i].c,v=N[i].a;
for (int k=; k<=c; k<<=)
{
value[count] = k*v;
size[count++] = k*v;
c -= k;
}
if (c > )
{
value[count] = c*v;
size[count++] = c*v;
}
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==&&m==)
break;
for(int i=; i <= m; i++)
f[i] = ;
ans=;
for(int i=;i<=n;i++)
scanf("%d",&N[i].a);
for(int i=;i<=n;i++)
scanf("%d",&N[i].c);
slove(n);
for(int i=;i<count;i++)
for(int gg=m;gg>=size[i];gg--)
f[gg]=max(f[gg],f[gg-size[i]]+value[i]);
for(int i=;i<=m;i++)
if(f[i]==i)
ans++;
cout<<ans<<endl;
}
return ;
}
最新文章
- 浅谈WebService的版本兼容性设计
- Oracle行转列操作
- 【AngularJS】—— 13 服务Service
- jsp学习---css基础知识学习,float,position,padding,div,margin
- Represent code in math equations
- MyEclipse10中导入的jquery文件报错(出现红叉叉,提示语法错误)
- MySQL Connector Net连接vs2012问题
- 網站SSL加密原理簡介(2张图,握手有9个步骤,解释的很清楚)
- PERL 实现微信登录
- PLSQL学习教程(全)
- 【C语言编程练习】7.1 线型表就地逆置
- 《Java8实战》读书笔记
- linux中ping带时间及打印内容到文件
- ansible基础命令实例
- 使用虚拟环境virtualenv/Virtualenvwrapper隔离多个python
- oracle(sql)基础篇系列(五)——PLSQL、游标、存储过程、触发器
- 在.NET环境下使用KAFKA
- 【本周主题】第三期 - JavaScript 内存机制
- oracle SQL语句取本周本月本年的数据
- 第21件事 资源支持离不开RACI表