poj-1276-Cash Machine-多重背包进行二进制转换
题意：

给总钱数mon，面额的种类数n；

每种面额有a张，面值大小为b；

求根据给出的面值组合出一个数，要求是小于等于mon的最大值。

做法：

用二进制转化。

比如说a=1124；b=10；

可以把这种货币转化成

1*10 2*10 4*10 8*10 16*10 32*10 64*10 128*10 256*10 512*10 101*10面额的钞票，每种一张，共11种。

因为用这11种钞票可以组合出任意1124张10元的所能组合出来的数。

#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int map[100001];int main(){    int i,j,mon,n,a,b;    while(scanf("%d %d",&mon,&n)!=EOF)    {        int size=0;        for(i=0;i<n;i++)        {            cin>>a>>b;            int s=1;            while(a)            {                a=a-s;                if(a<0)                {                    a=a+s;                    map[size++]=a*b;                    break;                }                map[size++]=s*b;                s=s*2;            }        }        int dp[100001],leap;        memset(dp,0,sizeof(dp));        leap=0;        for(i=0;i<size;i++)        {            for(j=mon;j>=map[i];j--)            {                if(dp[j]<dp[j-map[i]]+map[i])                    dp[j]=dp[j-map[i]]+map[i];            }        }       printf("%d\n",dp[mon]);    }    return 0;}