本文共 600 字，大约阅读时间需要 2 分钟。

题意：直接说数据，735是目标值，然后3是后面有三种钱币，四张125的，六张五块的和三张350的。

思路：能够轻易的看出这是一个多重背包问题，735是背包的容量，那些钱币是物品，而且有一定的数量，是多种背包。但是做的时候总是超时。可能是因为m和n太大。然后可以通过二进制把它转化为01背包，因为将钱币的数量化为二进制，1   2    4直到数量减一。化成的二进制数字排列组合，可以组成任意钱币数量内的数字。

看代码：

//二进制优化  多重背包转化为01背包#include
   
    int main(){    int cash,s[100010],n;    int dp[100010];    while(~scanf("%d%d",&cash,&n))    {        for(int i=0;i<=cash;i++)            dp[i]=0;        int k=0,a,b;        for(int i=0;i
    
     =s[i];j--)            {                dp[j]=dp[j]>dp[j-s[i]]+s[i]?dp[j]:dp[j-s[i]]+s[i];            }        }        printf("%d\n",dp[cash]);    }    return 0;}