题目链接：

题目大意：

Tony想要买一个东西，他只有n中硬币每种硬币的面值为a[i]每种硬币的数量为c[i]要买的物品价值不超过m

输入：第一行输入n和m，第二行输入n个硬币的面值和n个硬币的数量，输入0 0结束

输出：1到m之间有多少价格Tony可以支付

思路：

多重背包修改一下，如果dp[j-w[i]]可以到达，那么dp[j]也可到达

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int INF = 0x3f3f3f3f; 6 const int maxn = 200 + 10; 7 int T, n, m, cases; 8 int cost[maxn], amount[maxn]; 9 bool dp[100000 + 100];10 void zeroone(int cost)11 {12     for(int i = m; i >= cost; i--)13         if(dp[i - cost])dp[i] = dp[i - cost];14 }15 void complete(int cost)16 {17     for(int i = cost; i <= m; i++)18         if(dp[i - cost])dp[i] = dp[i - cost];19 }20 void solve(int cost, int amount)21 {22     if(cost * amount >= m)23         complete(cost);24     else25     {26         int k = 1;//二进制优化27         while(k <= amount)28         {29             zeroone(k * cost);30             amount -= k;31             k *= 2;32         }33         zeroone(amount * cost);34     }35 }36 int main()37 {38     while(cin >> n >> m && (n + m))39     {40         for(int i = 0; i < n; i++)cin >> cost[i];41         for(int i = 0; i < n; i++)cin >> amount[i];42         memset(dp, 0, sizeof(dp));43         dp[0] = 1;44         for(int i = 0; i < n; i++)45         {46             solve(cost[i], amount[i]);47         }48         int ans = 0;49         for(int i = 1; i <= m; i++)ans += dp[i];50         cout<
        
         <