如题：http://poj.org/problem?id=1742 Description People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were som

如题：http://poj.org/problem?id=1742   和之前那一篇hdu2844是一道题，但是这一题的数据量，用O（V*log2（Mi））的多重背包二进制拆分是超时的，为了缩短时间，必须更改dp数组的定义和状态转移方程     定义f[i][j]表示的是前i种硬币用来拼价值j，拼成后第i种硬币剩余的数量。 有j<w[i]，代表第i件物品1件都比价值j大，所

如题：http://poj.org/problem?id=1742 Coins Time Limit: 3000MS Memory Limit: 30000KTotal Submissions: 31258 Accepted: 10640 Description People in Silverland use coins.They have coins of value

给定N种硬币，其中第 i 种硬币的面值为Ai,共有Ci个。 从中选出若干个硬币，把面值相加，若结果为S，则称“面值S能被拼成”。 求1~M之间能被拼成的面值有多少个。 输入格式 输入包含多组测试用例。 每组测试用例第一行包含两个整数N和M。 第二行包含2N个整数，分别表示A1,A2,…,AN和C1,C2,…,CN。 当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。 输出格

题意： 给出n硬币的价值和个数，再给一个数值m，求在这些硬币能组成多少种总和（要求小于m） 要点： 与一般背包问题求最值不同，这里是求能有几种组合，应该是叫做背包的可行性问题，看了网上的代码，大体是用两个数组，一个储存总和是否出现过，一个储存当前硬币使用的数量。 15278156Seasonal1742Accepted1728K