【poj3093】Margaritas on the River Walk

2014年3月28日1,2180

Description

One of the more popular activities in San Antonio is to enjoy margaritas in the park along the river know as the River Walk. Margaritas may be purchased at many establishments along the River Walk from fancy hotels to Joe’s Taco and Margarita stand. (The problem is not to find out how Joe got a liquor license. That involves Texas politics and thus is much too difficult for an ACM contest problem.) The prices of the margaritas vary depending on the amount and quality of the ingredients and the ambience of the establishment. You have allocated a certain amount of money to sampling different margaritas.

Given the price of a single margarita (including applicable taxes and gratuities) at each of the various establishments and the amount allocated to sampling the margaritas, find out how many different maximal combinations, choosing at most one margarita from each establishment, you can purchase. A valid combination must have a total price no more than the allocated amount and the unused amount (allocated amount – total price) must be less than the price of any establishment that was not selected. (Otherwise you could add that establishment to the combination.)

For example, suppose you have $25 to spend and the prices (whole dollar amounts) are:

Vendor A B C D H J
Price 8 9 8 7 16 5

Then possible combinations (with their prices) are:

ABC(25), ABD(24), ABJ(22), ACD(23), ACJ(21), ADJ( 20), AH(24), BCD(24), BCJ(22), BDJ(21), BH(25), CDJ(20), CH(24), DH(23) and HJ(21).

Thus the total number of combinations is 15.

Input

The input begins with a line containing an integer value specifying the number of datasets that follow, N (1 ≤ N ≤ 1000). Each dataset starts with a line containing two integer values Vand D representing the number of vendors (1 ≤ V ≤ 30) and the dollar amount to spend (1 ≤ D ≤ 1000) respectively. The two values will be separated by one or more spaces. The remainder of each dataset consists of one or more lines, each containing one or more integer values representing the cost of a margarita for each vendor. There will be a total of V cost values specified. The cost of a margarita is always at least one (1). Input values will be chosen so the result will fit in a 32 bit unsigned integer.

Output

For each problem instance, the output will be a single line containing the dataset number, followed by a single space and then the number of combinations for that problem instance.

Sample Input

Sample Output

题解

1. 特殊情况,一个都放不进去,就是剩下物品中体积最小的那个都放不进去,这个情况就会无解,答案为0;

2. 一般情况:从小到大枚举不放入背包的体积最小的,那么此时比它小的物品都应该放入背包中,此时背包容量应为[m-s[i]+1,m](1<=i<=n)

我们可以对剩下的的物品做01背包,然后将可行的方案统计出来,这样,第u件物品考虑了i-1次,总复杂度为O(n^2*m);

优化:

n较大的话会超时,我们可以反过来做,每个物品只放入背包中一次,即枚举的时候从最大的开始,先统计此时的方案数,然后将物品放入背包,这样一直下去,总复杂度O(n*m)

好像不是很好理解,具体看代码