HDU 2844 Coin 多重背包
2024-08-25 23:07:50
Coins
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6279 Accepted Submission(s): 2561
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.
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.
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
Sample Output
8
4
题解:英语不好,果然个个都赶脚是坑啊,唉,题意千万读懂了再做题,本题是多重背包的题目,A 表示硬币的价值, C 表示对应硬币的数量;典型的完全背包啊;
1.首先是 n 表示 n 组数据,第一行输入价值 A, 第二行输入价值对应的数量 C ;用这些价值的硬币,组合出在 1 和 m ,之间的数(包括1,m);
2.所以我们可以把,多重背包分成 01 和 完全背包 来解;如果遇见 A[i]*[i]>=m 按照完全背包,否则 01 背包;
AC代码一:
#include<stdio.h>
#include<string.h>
#include<algorithm>
int v[];
int w[];
int dp[];
using namespace std;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==)
break;
memset(v,,sizeof(v));
memset(w,,sizeof(w));
for(int i=;i<=;i++)
dp[i]=-;
dp[]=;
for(int i=; i<=n; i++)
scanf("%d",&v[i]);
for(int i=; i<=n; i++)
scanf("%d",&w[i]);
for(int i=; i<=n; i++)
{
if(v[i]*w[i]>=m)//完全背包
{
for(int j=v[i]; j<=m; j++)
{
dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
}
}
else
{
for(int k=; k<=w[i]; k=k*)
{
for(int j=m; j>=v[i]*k; j--)
{
dp[j]=max(dp[j],dp[j-v[i]*k]+v[i]*k);
}
w[i]-=k;
}
if(w[i]>)
{
for(int j=m; j>=v[i]*w[i]; j--)
dp[j]=max(dp[j],dp[j-v[i]*w[i]]+v[i]*w[i]);
}
}
}
int count=;
for(int i=; i<=m; i++)
{
if(dp[i]>=)
count++;
}
printf("%d\n",count);
}
return ;
}
AC代码二:
#include<iostream>
#include<string.h>
using namespace std; int a[],c[],F[]; void inline ZeroOnePack(int ResVal,int ResVol,int BpCap)
{
for(int i=BpCap;i>=ResVol;--i)
{
F[i]=max(F[i],F[i-ResVol]+ResVal);
}
} void inline CompletePack(int ResVal,int ResVol,int BpCap)
{
for(int i=ResVol;i<=BpCap;++i)
{
F[i]=max(F[i],F[i-ResVol]+ResVal);
}
} void MultiplePack(int ResVal,int ResVol,int ResNum,int BpCap)
{
if(ResVol*ResNum>=BpCap)
{ CompletePack(ResVal,ResVol,BpCap); }
for(int i=;(<<i)<=ResNum;++i)
{
ZeroOnePack((ResVal<<i),(ResVol<<i),BpCap);
ResNum-=(<<i);
}
if(ResNum) { ZeroOnePack(ResVal*ResNum,ResVol*ResNum,BpCap); }
} int main()
{
int i,j,n,m;
while(cin>>n>>m)
{
if(n+m==)
break;
memset(F,,sizeof(F));
for(i=;i<n;i++)
cin>>a[i];
for(j=;j<n;j++)
cin>>c[j];
for(i=;i<n;i++)
{
MultiplePack(a[i],a[i],c[i],m) ;
}
int num=;
for(i=;i<=m;i++)
{
if(F[i]==i)
num++;
}
cout<<num<<endl;
}
return ;
}
最新文章
- 使用HttpURLConnection下载图片
- 浅谈游标选项 Static|Keyset|DYNAMIC|FAST_FORWARD
- SQL请求优化——请求次数统计,SQL写操作稀释
- 字符串—strcpy
- maven 仓库搜索添加需要的jar包
- THE HANDLER_READ_* STATUS VARIABLES
- NAT地址转换原理全攻略
- WPFS数据绑定(要是后台类对象的属性值发生改变,通知在“client界面与之绑定的控件值”也发生改变须要实现INotitypropertyChanged接口)
- poj2762 Going from u to v or from v to u?
- 控制台下的计算器——C++实现
- clear:both后margin-top不起作用
- [Git]07 如何在提交过程中忽略某些文件
- Oracle中使用游标转换数据表中指定字段内容格式(拼音转数字)
- mybatis源码之BaseStatementHandler
- Java 学习体系结构
- React Hooks (React v16.7.0-alpha)
- kamailio 云部署 配置NAT
- 操作系统组成和工作原理以及cpu的工作原理
- Ehcache缓存配置以及基本使用
- 【BZOJ1417】Pku3156 Interconnect