题目代号:POJ 3260

题目链接:http://poj.org/problem?id=3260

The Fewest Coins

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 6715 Accepted: 2072

Description

Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number is.

FJ wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, ..., VN (1 ≤ Vi ≤ 120). Farmer John is carrying C1 coins of value V1, C2 coins of value V2, ...., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner (although Farmer John must be sure to pay in a way that makes it possible to make the correct change).

Input

Line 1: Two space-separated integers: N and T.

Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1, ...VN)

Line 3: N space-separated integers, respectively C1, C2, ..., CN

Output

Line 1: A line containing a single integer, the minimum number of coins involved in a payment and change-making. If it is impossible for Farmer John to pay and receive exact change, output -1.

Sample Input

3 70
5 25 50
5 2 1

Sample Output

3

Hint

Farmer John pays 75 cents using a 50 cents and a 25 cents coin, and receives a 5 cents coin in change, for a total of 3 coins used in the transaction.

题目大意:给你N种面值的钱以及买家所拥有的数量(注意:卖家的没种面值的钱是无限的),要买T价值的东西,问:要使给出的钱和收到的钱数量最小,然后求总和就是答案。

题目分析:对于买家来说,这是一个多重背包问题,对于卖家来说,这是一个完全背包问题,所以这个题是多重背包和完全背包组合而成的混合背包问题,由于背包问题都是由01背包衍生和优化出来的,所以需要对于01背包的思想完全掌握和熟练运用。然后另一个问题就是这个背包容量的上限问题,在我们生活之中如果需要买1269元的东西那么我们需要给出12张100元面值的,1张50元面值的,1张10元面值的,1张5元面值的,4张1元面值的,合计19张,那么如果按照题目中的要求我可以付款13~18张的100面值的钱,18显然比19要少,但是给了超过1300元的面值的100元都会被卖家原样找回,这很显然是没有必要的,因为在最优的答案之中找的钱不会超过100元,这个题目中也是这样,然后根据抽屉原理,多重背包容量的上限为T+max*max(max即为最大面值的钱),完全背包的上限为T+max。(别问我,我也不知道怎么来的,记住就好了,实在不会那就数组开大点。。。)

AC代码:

# include <bits/stdc++.h>
using namespace std;
# define mem(a,b) memset(a,b,sizeof(a))
# define IOS ios::sync_with_stdio(false);
# define FO(i,n,a) for(int i=n; i>=a; --i)
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define MAX 0x7fffffffffffff
# define INF 0x3f3f3f3f
# define MOD 1000000007
/// 123456789
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef unsigned long long ULL;
typedef long long LL;
///coding...................................
const int MAXM=30005;
int n,m,c[105],v[105],sum;
int b[MAXM],a[MAXM]; void complete_bag(int *dp,int vis) {
FOR(i,vis,sum)
dp[i]=min(dp[i],dp[i-vis]+1);
} void zero_one_bag(int *dp,int vis,int cost) {
FO(i,sum,vis)
dp[i]=min(dp[i],dp[i-vis]+cost);
} void mult_bag(int *dp,int vis,int cost) {
if(vis*cost>=sum)complete_bag(dp,vis);
else{
int cnt=1;
while(cnt<=cost){
zero_one_bag(dp,vis*cnt,cnt);
cost-=cnt;
cnt<<=1;
}
if(cost)zero_one_bag(dp,vis*cost,cost);
}
} int main()
{
IOS
#ifdef FLAG
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif /// FLAG
while(cin>>n>>m) {
sum=0;
for(int i=0;i<n;i++)
cin>>v[i],sum=max(sum,v[i]);
for(int i=0;i<n;i++)cin>>c[i];
sum=m+sum*sum;
for(int i=1;i<=sum;i++)a[i]=b[i]=INF;
b[0]=a[0]=0;
for(int i=0;i<n;i++)complete_bag(a,v[i]);
for(int i=0;i<n;i++)mult_bag(b,v[i],c[i]);
int ans=INF;
for(int i=m;i<=sum;i++)
if(b[i]+a[i-m]<ans)
ans=b[i]+a[i-m];
if(ans==INF)puts("-1");
else cout<<ans<<endl;
}
return 0;
}

最新文章

  1. java中this 关键字的使用
  2. CocoaPods常用终端命令及Profile文件简单介绍
  3. background-origin 设置背景图片原始起始位置
  4. oracle数据库解析json格式
  5. 求Mac 的adt插件!
  6. ERP_基于Oracle SOA的企业服务总线整合
  7. 关于server的一些小记
  8. 代码自动生成工具MyGeneration之一(程序员必备工具)
  9. 触发器-Trigger
  10. poj 1170 Shopping Offers
  11. BZOJ 1001 狼捉兔子
  12. Entity Framwork db First 中 Model验证解决办法。
  13. bitmap 内存溢出OOM的解决办法分享
  14. 让低版本的IE浏览器 强制渲染为IE8 或者 以上 浏览器模式
  15. hdu_2838_Cow Sorting(树状数组求逆序对)
  16. excel 下拉级联,重新选第一个,清空后一个已赋值,并且改变后一个下拉的内容。
  17. IntelliJ IDEA 创建maven管理的webapp项目
  18. Nginx 反向代理504 Gateway Time-out
  19. BZOJ3676 APIO2014 回文串 Manacher、SA
  20. 基于Spring Cloud的微服务落地

热门文章

  1. CDH6.2扩容
  2. Spring MVC 中使用AOP 进行统一日志管理--注解实现
  3. Python 对于分表的操作
  4. fid解释
  5. numpy-添加操作大全
  6. 使用油猴子 greasemonkey xx 百度 ...
  7. linux 配置环境变量三种方式
  8. 搜索框focus 搜索面板显示 点击别处消失 从浏览器别的页面回来消失
  9. MATLAB中的函数句柄及其应用
  10. Docker 镜像 容器 仓库