margaritas on the River Walk(01 가방 통계)

Margaritas on the River Walk
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 2126
 
Accepted: 792
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 toJoe’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
팔
구
팔
칠
십육
오
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 V and 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

2
6 25
8 9 8 7 16 5
30 250
1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

Sample Output

1 15
2 16509438

Hint
Note: Some solution methods for this problem may be exponential in the number of vendors. For these methods, the time limit may be exceeded on problem instances with a large number of vendors such as the second example below.
Source
Greater New York 2006
제목:http://poj.org/problem?id=3093
제목: n개의 물품과 하나의 총 돈수 m를 주고 실행 가능한 방안의 총수를 구한다. 즉, 몇 개의 물품을 샀고 돈의 수가 범위를 초과하지 않으며 구매하지 않은 물품 중의 최소 가치가 남은 돈보다 작다는 것이다.
분석: 한 개의 물품을 일일이 열거하여 사지 않으면 가격이 그 물품보다 작으면 모두 사야 한다. 가격이 그 물품보다 크면 01배낭으로 통계하면 된다. 상태 이동 방정식은
f[i]=sum {f[i-v[j]]]}j는 현재 사지 않는 물품보다 가격이 높습니다. v[j]<=i, 이것은 먼저 가격에 따라 정렬해야 합니다.
이러한 복잡도는 O(n^2*m)로 분명히 시간을 초과해야 한다. 데이터가 약하면 초과하지 않을 것 같다=
사실 최적화는 매우 간단하다. 바로 거꾸로 물건을 일일이 열거하면 된다. 01배낭의 물품에 참여할 때마다 비슷한 것이 하나 더 많아졌기 때문에 모든 물건은 하나만 만들 수 있는 배낭이다.
복잡도 O(n*m)
몇 조의 틀리기 쉬운 데이터
3 29 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 29 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 30 466 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
코드:

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int mm=1111;
int f[mm],v[mm];
int i,j,k,n,m,c,ans,t,cs=0;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<=m;++i)f[i]=0;
        f[0]=1,c=m;
        for(i=0;i<n;++i)
            scanf("%d",&v[i]),c-=v[i];
        sort(v,v+n);
        ans=(c>=0);
        if(v[0]<=m)
        for(i=n-1;i>=0;--i)
        {
            if((c=c+v[i])>=0)
                for(j=max(0,c-v[i]+1);j<=c;++j)ans+=f[j];
            for(j=m;j>=v[i];--j)f[j]+=f[j-v[i]];
        }
        printf("%d %d
",++cs,ans);
    }
    return 0;
}