用多重背包划归成0-1背包做的，数组大小应该没问题

#include <iostream>
#include <cstring>
using namespace std;
int max(int i,int j){
        return i>j?i:j;
}
int main(){
        int cash,kind_of_bill;
        int number_of_bill[15],deno_of_bill[15];//每种硬币的数量及面值
        int transformed[120];//利用多重背包问题的转化
        int demon[14]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192};//保存2的k次幂
        int packet[100010];
        while(cin>>cash>>kind_of_bill){
                for(int i=0;i<kind_of_bill;i++)
                        cin>>number_of_bill[i]>>deno_of_bill[i];
                int j=0;
                //将多重背包化为0-1背包
                for(int i=0;i<kind_of_bill;i++){
                        int k=0;
                        while (number_of_bill[i]>demon[k])  {
                                transformed[j++]=demon[k++]*deno_of_bill[i];
                                number_of_bill[i]=number_of_bill[i]-demon[k];
                        }
                        transformed[j++]=number_of_bill[i]*deno_of_bill[i];
                }
                //化归完成
                memset(packet,0,sizeof(packet));
                for(int i=0;i<j;i++){
                        for(int k=cash;k>=0;k--){
                                if(i==0){
                                        if(k>=transformed[i])
                                                packet[k]=transformed[i];
                                        else
                                                packet[k]=0;
                                }
                                else{
                                        if(k>=transformed[i]){
                                                packet[k]=max(packet[k],packet[k-transformed[i]]+transformed[i]);
                                        }
                                }
                        }
                }
                cout<<packet[cash]<<endl;
        }
        return 0;
}