#include<iostream>
#include<climits>
using namespace std;
int m[10000];
struct coin
{
int value;
int weight;
}s1[1000];
main()
{
int t,w0,w1,n,temp,temp1,i,j,w;
cin>>t;
while(t--)
{
cin>>w0>>w1;
w=w1-w0;
cin>>n;
temp1=INT_MAX;
for(i=1;i<=n;i++)
{
cin>>s1[i].value>>s1[i].weight;
if(temp1>s1[i].weight)
temp1=s1[i].weight;
}
for(i=0;i<temp1;i++)
m[i]=0;
for(i=temp1;i<=w;i++)
{
temp1=INT_MAX;
for(j=1;j<=n;j++)
{
temp=0;
if(i-s1[j].weight>=0)
{
if(m[i-s1[j].weight]>0 || i==s1[j].weight)
temp=m[i-s1[j].weight]+s1[j].value;
}
if(temp<temp1 && temp!=0)
temp1=temp;
}
if(temp1==INT_MAX)
m[i]=0;
else
m[i]=temp1;
}
if(!m[w])
cout<<"This is impossible."<<endl;
else
{
cout<<"The minimum amount of money in the piggy-bank is "
<<m[w]<<"."<<endl;
}
}
}
This is my code ....
On Sun, Dec 5, 2010 at 2:01 PM, Bharath 2009503507 CSE <
[email protected]> wrote:
> i am a beginner.pl help me with this code.i submitted a solution.it s
> giving op for all given testcases.but the judge is giving me a TLE.
>
> code:
>
> #include<iostream>
> #include<map>
> #define inf 999999999
> using namespace std;
> map<int,int> m2;
> int func(map<int,int> &m1,int w)
> {
> if(m2[w]<inf)
> return m2[w];
> map<int,int>::iterator it;
> int min=inf;
> for(it=m1.begin();it!=m1.end();it++)
> {
> if((*it).second<=w)
> {
> int x=func(m1,w-(*it).second);
> if(x+(*it).first < min)
> min=x+(*it).first;
> }
> }
> m2[w]=min;
> return min;
> }
>
> main()
> {
> int t;
> cin>>t;
> while(t--)
> {
> int w1,w2;
> cin>>w1>>w2;
> int w=w2-w1,no,a,b;
> cin>>no;
> map<int,int> m1;
> for(int i=0;i<no;i++)
> {
> cin>>a>>b;
> m1.insert(pair<int,int>(a,b));
> }
> m2[0]=0;
> for(int i=1;i<=w;i++)
> m2[i]=inf;
> func(m1,w);
> if(m2[w]!=inf)
> cout<<"The minimum amount of money in the piggy-bank is
> "<<m2[w]<<".\n";
> else
> cout<<"This is impossible.\n";
> }
> }
>
>
> pl say hw i can improve.
> thanks in advance.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
