转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
买家的硬币是有限制的,是多重背包。
卖家每种硬币没有限制,是完全背包。
dp_buy[i]表示买家凑齐i需要的最少硬币个数。
dp_sale[i]表示专家凑齐i需要的最少硬币个数。
但是背包上界不好定,开始以前是专家为m,买家是2*m,结果是WA。
对于这组数据
2 1
3 100
100 100
就可以 看得清楚,所需只有1,但是容量远不止2*m,一怒之下改为m+10000
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-6
#define LL long long
#define LD long double
#define pi acos(-1.0)
#define inf 1<<25
using namespace std;
int n,m,cnt[105],val[105];
int dp_buy[20005],dp_sale[20005];
void completepack(int *dp,int cost,int limit){
for(int i=cost;i<=limit;i++)
dp[i]=min(dp[i],dp[i-cost]+1);
}
void zeroonepack(int *dp,int cost,int limit,int count){
for(int i=limit;i>=cost;i--)
dp[i]=min(dp[i],dp[i-cost]+count);
}
void doublepack(int *dp,int cost,int count,int limit){
if(cost*count>=limit)
completepack(dp,cost,limit);
else{
int tmp=1;
while(tmp<=count){
zeroonepack(dp,cost*tmp,limit,tmp);
count-=tmp;
tmp<<=1;
}
if(count)
zeroonepack(dp,cost*count,limit,count);
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<n;i++)
scanf("%d",&val[i]);
for(int i=0;i<n;i++)
scanf("%d",&cnt[i]);
for(int i=1;i<=m+10000;i++)
dp_sale[i]=inf;
for(int i=1;i<=m+10000;i++)
dp_buy[i]=inf;
dp_buy[0]=dp_sale[0]=0;
for(int i=0;i<n;i++)
completepack(dp_sale,val[i],m+10000);
for(int i=0;i<n;i++)
doublepack(dp_buy,val[i],cnt[i],m+10000);
int ans=inf;
for(int i=m;i<=m+10000;i++)
if(dp_buy[i]+dp_sale[i-m]<ans)
ans=dp_buy[i]+dp_sale[i-m];
if(ans==inf)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
poj 3260 The Fewest Coins.md
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1163-The Triangle 解题报告+AC代码
晒代码之二——多重背包(POJ1276)
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ初级题-数据结构:解题报告+AC代码
poj 1611 The Suspects 代码 并查集的应用
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
北大POJ2187-Beauty Contest 解题报告+AC代码
北大POJ3252-Round Numbers 解题报告+AC代码