A来B处买东西，价值M元，有N种钱，每种钱A有一定数量，而B有无限数量。

求最少用多少张钞票可以满足交易，比如样例，A出50+25，B找5，即可满足，需要3张。

A用多重背包转移状态，B用完全背包。

本文的多重背包优化用的是O（n）算法，二进制转换的O（nlogn）实在懒得写了。

那种可以看http://blog.csdn.net/vmurder/article/details/39472419

“ 

【POJ1014】Dividing 多重背包，二进制物品拆分转01背包

贴代码：

#include 
#include 
#include 
#define N 150
#define M 20000
#define inf 0x3f3f3f3f
using namespace std;int n,m,ans=inf;
int w[N],num[N];
int f1[M],cnt[M],f2[M];
int main()
{
//	freopen("test.in","r",stdin);int i,j,k;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&w[i]);for(i=1;i<=n;i++)scanf("%d",&num[i]);memset(f1,0x3f,sizeof(f1));memset(f2,0x3f,sizeof(f2));f1[0]=f2[0]=0;for(i=1;i<=n;i++){memset(cnt,0,sizeof(cnt));for(j=w[i];j<=15000;j++){if(f1[j]>f1[j-w[i]]+1&&cnt[j-w[i]]=15000)printf("-1\n");else printf("%d\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！