`
java-mans
  • 浏览: 11343965 次
文章分类
社区版块
存档分类
最新评论

POJ 3260 The Fewest Coins 多重背包+完全背包

 
阅读更多

转载请注明出处,谢谢 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;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics