HU-236 Buy the souvenirs

4644 ワード

配列01リュックサック
http://acm.hdu.edu.cn/showproblem.php?pid=2126
http://blog.csdn.net/crazy_ac/articale/detail/7869411
f[i][j][k]は前のi種のものを表して、j個を買って、kに等しいお金を使った時の方案数を表します.
k以下ですので、初期化の時は注意してください.
じゃ移転する時はi番目のものを取りますか?取りません.
 f[i][j]、[k]+=f[i-1][j][k]   f[i][j]+=f[i-1][j-1][k-v[i];
                      Buy the souvenirs
Time Limit:10000/1000 MS(Java/Others)    メモリLimit:32768/32768 K(Java/Others)Total Submission(s):748    Acceepted Submission(s):255
Problem Description
When the winder holiday coes、a lot of people will have a trip.Geneneraally、there ara lot of souvevenirs to sell、and sometimes the trtrvelers will bus some ons with th pleaeaeasure.Not only can Alalalalalalalalalalalalalalalalalalallycan cancan the they thethey thetheythethethethethethethethetheyyyythethethethethethethe SoSoininininininininininininininininininininininininininininininininininininininininininininininall、the prices of souvenirs are not very dear,and the souvenirs are also lovable and interesting.But the money the people have is under the control.Thy can’t buy a lot,but only the might the and the the mondarybut there re re re no two ons with the same kind in any commbination.Now there is a blank written by the names and prices of the souvens、asa top coder all around the world、you shuld calculate hony sections the and hantiness
And you have only 7 RMB、this time you can select any commbination with 3 kids of souvens at most、so the selections of 3 kids of ABC souvensare(6)、ABD(7).But if you have 8 RMB、the selectious with mokins.inds,ABDthere is only one selection with the most kids of souvenirs to you:ABCD(10)
 
Input
For the first line,there is a T means the number cases,the n T cases follow.In each case,in the first line there re re re re to integer n and m,n is the number of the souvenirs and m is m the mon the monyes have.The congente.Themens.The conteline conteline.each integer describes a kind of souvenir.
All the numbers and result are in the range of 32-signed integer、and 0<=m==500、0<=30、t<=500、and the press are integers.The is a blank line between woses.
 
Output
If You Can buy some souvenirs,You shuld print the reresit with the same formation as「You have S selection(s)to buy with K kind(s)of souveirs」,where the K means the most kinds of souvevens Can bububuy,thenbububububuininininininininininininininininininininininininininininininininininininininininininininininininininininininininstststststststststststststststststststininininininininininininininy nothing、so you must print the result"Sorry,you can't buy anything."
 
Sample Input
2
4 7
1 2 3 4
4 0
1 2 3 4
 
Sample Output
You have 2 selection(s)to buy with 3 kind(s)of souvens.
Sorry,you can't buy anything.
#include<iostream>
#include<cstring>
using namespace std;
int f[50][50][510],v[50];
int n,m,ans1,ans2;
int fun()
{
    int i,j,k;
    for(i=n;i>0;i--)
      for(j=i;j>0;j--)
         for(k=m;k>=0;k--)
           if(f[i][j][k])
                {
                    ans1=f[i][j][k];
                    ans2=j;
                    return 1;

                }


         return 0;
}
int main()
{
    int i,j,k,t;
    cin>>t;
    while(t--)
    {

        memset(v,0,sizeof(v));
        cin>>n>>m;
        for(i=1;i<=n;i++)
           cin>>v[i];
          memset(f, 0, sizeof(f));
             for(i = 0; i <= n; i++)
               for(j = 0; j <= m; j++)
                  f[i][0][j] = 1;
         for(i=1;i<=n;i++)
          for(j=1;j<=i;j++)
            for(k=m;k>=0;k--)
              {
                 f[i][j][k]+=f[i-1][j][k];
                 if(k>=v[i])
                   f[i][j][k]+=f[i-1][j-1][k-v[i]];
              }
              if(fun())
                 cout<<"You have "<<ans1<<" selection(s) to buy with "<<ans2<<" kind(s) of souvenirs."<<endl;
              else
                 cout<<"Sorry, you can't buy anything."<<endl;
        }
        return 0;
    }