UVa 990 – Diving for Gold

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=931

Solution Idea:

This is a classical knapsack problem. But in this problem we have to print the maximum profit as well as the detailed solution that is the maximum solution is obtained from which objects. Here the cost/weight is given by two equations like this-

• The descent time is tdi = w ∗ d[i] , where w is an integer constant.

• The ascent time is tai = 2w ∗ d[i] , where w is an integer constant.

So we can say that total cost/time need to get this treasure =  descent time+ascent time . which is w*d[i] + 2*w*d[i]=3*w*d[i].

Now we have to run a knapsack and we have to mark the objects which give me maximum profit. Now we have an array called path[][] which is initially set as -1 and it will mark the optimal objects. In knapsack function we have to variable p and q . where –

p= profit for taking current object

q=profit without current object

So if p>q then we will mark path[idx][air] = 1 else path[idx][air] = 2.

Now we have another function named path_print(idx, air) for getting the correct route of solution. In this function-

  • If path[idx][air] = 1 Then we will take the current objects and jump to  (idx+1, air+ 3*w*d[idx]) state.
  • If path[idx][air] = 2 then we will skip the current objects and jump to  (idx+1,air) state.
  • If path[idx][air] = -1 then we will stop because we already take the optimal objects.

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int t,w,n;
int d[40],v[40];

int dp[40][1100];
int path[40][1100];

int func(int idx, int air)
{
    if(idx>=n) return 0;

    int &ret=dp[idx][air];
    if(ret!=-1) return ret;

    int p=0,q=0;

    if((air+(3*w*d[idx]))<=t)
        p=v[idx]+func(idx+1,air+(3*w*d[idx]));
    q=func(idx+1,air);

    if(p>q) path[idx][air]=1;
    else path[idx][air]=2;

    return ret=max(p,q);
}

vector<int>ans;

int path_print(int idx, int air)
{
    if(path[idx][air]==-1) return 0;

    if(path[idx][air]==1)
    {
        ans.pb(idx);
        return 1+path_print(idx+1,air+(3*w*d[idx]));
    }
    else
        return path_print(idx+1,air);
}

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    bool test=0;

    while(sff(t,w)==2)
    {
        if(test==1) pf("\n");
        test=1;
        sf(n);
        loop(i,n) sff(d[i],v[i]);
        ms(dp,-1);
        ms(path,-1);
        int profit=func(0,0);

        pf("%d\n",profit);
        pf("%d\n",path_print(0,0));
        loop(i,SZ(ans))
        pf("%d %d\n",d[ans[i]],v[ans[i]]);
        ans.clear();
    }

    return 0;
}


UVa 1213 – Sum of Different Primes

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3654

Solution Idea:

This problem is similar to Uva 10616 – Divisible Group Sums . This one can be solved using knapsack or Coin change. In this problem the objects or coins are prime numbers. So at first we calculate the prime numbers using sieve algorithm in the given range of input.

Then we simply call a dp function and show the ans. In this problem the value of objects or coins is not changing in every cases so we need not to clear the dp array every time. We just calculate the process backwards in dp function.


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


vector<int> prime;
bool visit[1130];
int n,k;

void sieve()
{
    for(int i=2;i<1130;)
    {
        prime.pb(i);
        for(int j=i+i;j<1130;j+=i)
            visit[j]=1;
        for(++i;;i++) if(visit[i]==0) break;
    }
}

ll dp[195][15][1130];

ll func(int idx, int cnt, int sum)
{
    if(cnt==0)
    {
        if(sum==0) return 1;
        return 0;
    }

    if(idx>=SZ(prime)) return 0;

    ll &ret=dp[idx][cnt][sum];

    if(ret!=-1) return ret;

    int p=0,q=0;

    if(sum-prime[idx]>=0) p=func(idx+1,cnt-1,sum-prime[idx]);
    q=func(idx+1,cnt,sum);

    return ret=p+q;
}


int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    sieve();

    ms(dp,-1);

    while(sff(n,k)==2 && (n && k))
    {
        ll ans=func(0,k,n);
        pf("%lld\n",ans);
    }

    return 0;
}


UVa 10130 – SuperSale

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1071

Solution Idea:

This is a classical knapsack problem. Just run a knapsack for every persons capacity and sum up the price taken by that person. total sum is the ans.

In this problem we need not to clear the whole dp array for every person. Because the weight and price is not changing for every person. they remain same all the time for a test case. So we have to clear the dp array once for every test case.


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n,price[1100],weight[1100];

int dp[1005][40];

int func(int idx, int w)
{
    if(idx>=n) return 0;

    int &ret=dp[idx][w];

    if(ret!=-1) return ret;

    int p=0,q=0;

    if(w-weight[idx]>=0) p=price[idx]+func(idx+1,w-weight[idx]);

    q=func(idx+1,w);

    return ret=max(p,q);
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        sf(n);
        loop(i,n) sff(price[i],weight[i]);
        ms(dp,-1);
        ll ans=0;
        int g;
        sf(g);
        while(g--)
        {
            int a;
            sf(a);
            ans+=func(0,a);
        }
        pf("%lld\n",ans);
    }

    return 0;
}


UVa 10616 – Divisible Group Sums

1

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1557

Solution Idea:

This is a knapsack problem where the given numbers are objects. we have to count how many set is there of size m whose sum is divisible by d.

Now here we have a three state dp. where idx indicates the current index of objects, cnt indicates how many objects we have taken till now and we can’t take more than m element and this is a base case. and 3rd parameter is sum, which indicates the sum of the objects we have taken till now.

Now the sum can be very large and we can’t store the original sum in our dp array because we can’t declare such large array. So we can store the (sum%d) in the array because (sum%d) < 20  so we can easily store that. so in every step we have two call one is by taking current object and another is without taking that object. and the base case is when we have taken m elements then the sum value is either 0 or not. if it is a zero then we can say that it is divisible by d.

Now the most tricky part in this problem is the numbers can be negative and we have to consider how to mod the negative numbers. Lets see a example-

-12 % 7 = ??

If we calculate through computer or calculator the output will be -5. but is this correct??

Normally a%b = (a-x)

Where x is the greatest element which is divisible by b and which is less than or equal to a.

So we can say that x%b==0 and x<=a.

Now lets find the number x for -12 . we can see that -14 is the greatest element which is divisible by 7 and which is less than or equal to -12.

So the correct ans for -12%7 = (-12-(-14))= -12+14=2 😛

We can calculate the modulus result easily in this way.

if the operation is a%b and a<0. then the correct modulus value will be (a%b)+b.

-12%7= (-12%7)+7=-5+7=2 😀

So in this problem we have to consider the modulus of negative numbers.


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n, q,d,m;
int ara[300];
ll dp[210][11][22];

ll func(int idx, int cnt, int sum)
{

    if(cnt==m)
    {
        if(sum==0) return 1;
        return 0;
    }
    if(idx>=n) return 0;

    ll &ret=dp[idx][cnt][sum];

    if(ret!=-1) return ret;


    ll xx=0,yy=0;

    ll temp=sum+ara[idx];
    temp%=d;
    if(temp<0) temp+=d;

    xx=func(idx+1,cnt+1,temp);

    yy=func(idx+1,cnt,(sum)%d);

    return ret=xx+yy;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int z=0;

    while(sff(n,q)==2 && (n && q))
    {
        z++;
        pf("SET %d:\n",z);
        loop(i,n) sf(ara[i]);
        loop(i,q)
        {

            sff(d,m);
            ms(dp,-1);
            printf("QUERY %d: %lld\n",i+1,func(0,0,0));
        }
    }

    return 0;
}

UVa 10664 – Luggage

0

Problem Link :https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1605

Solution Idea:

The main problem is an array of integers is given and we have to divide the array into two small array in such a way so that the sum of both arrays are same.

At first we take input and sum up the array values. if the total sum is odd then it’s confirm that we can’t split it into two equal sum. so that we can output “NO”.

If the sum is Even then we can use knapsack of Coin Change any algorithm to check if we can make the (sum/2) value from the given array values. Here I am using knapsack.

As the input of this problem is tricky because we don’t know how many numbers there will be in a line. So for this problem I use stringstream to solve this problem.


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

vector<int> v;

int dp[30][110];

int knapsack(int idx, int val)
{
    if(val==0) return 1;
    if(idx==SZ(v)) return 0;

    int &ret=dp[idx][val];
    if(ret!=-1) return ret;

    int p=0,q=0;

    if(val-v[idx]>=0) p=knapsack(idx+1,val-v[idx]);
    q=knapsack(idx+1,val);

    return ret=p|q;

}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int m;
    cin>>m;
    getchar();
    while(m--)
    {
        string str;
        getline(cin,str);
        stringstream ss;
        ss<<str;
        int val;
        int sum=0;
        while(ss>>val)
        {
            v.pb(val);
            sum+=val;
        }

        if(sum & 1)
            cout<<"NO"<<endl;
        else
        {
            ms(dp,-1);
            if(knapsack(0,sum/2))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }

        v.clear();


    }

    return 0;
}

UVa 10819 – Trouble of 13-Dots

0

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1760

Solution idea:

This is a classical knapsack problem. Set a correct base case is the most challenging part of this problem. If we read and think carefully about this problem we can see that if the expense exceeds 2000$ then 200$ will be refunded so it will be strictly greater than 2000. Now we can consider 3 things as base case. Those are here-

Let W is expense at current time and C = capacity or Total money.

  •  When W > Capacity and W-Capacity > 200 then we can’t buy anything else and the current product so we will return a large negative value to cancel this solution.
  • When Capacity < 1800 and Capacity < W then it's clear we can't buy anything and current product so we will cancel this.
  •  And Last thing is when we are taking the last product then if W > Capacity and W <= 2000 then we can take these so we will return a Zero. Otherwise we will cancel this one by returning a large negative value.

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int capacity, n;

int z;

int dp[110][10300];
int weight[110],profit[110];

int knapsack(int idx, int w)
{
    if(w>capacity && w-capacity>200) return -100000;
    if(capacity<1800 && w>capacity) return -100000;

    if(idx==n)
    {
        if(w>capacity && w<=2000) return -100000;
        return 0;
    }

    if(dp[idx][w]!=-1) return dp[idx][w];

    return dp[idx][w]=max(profit[idx]+knapsack(idx+1,w+weight[idx]),knapsack(idx+1,w));
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    CIN;
    while(cin>>capacity>>n)
    {
        z++;
        loop(i,n) cin>>weight[i]>>profit[i];

        ms(dp,-1);
        cout<<knapsack(0,0)<<endl;


    }

    return 0;
}

Here is another solution 🙂


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int capacity, n;

pii input[110];
int z;
int dp[110][10210];
int cases[110][10210];
bool test=0;

int knapsack(int idx, int w)
{
    if(w==capacity)
    {
        return 0;
    }
    if(idx>=n) return 0;
    int &ret=dp[idx][w];
    int &cas=cases[idx][w];

    if(cas==z) return ret;

    cas=z;

    int p=0,q=0;

    if(w+input[idx].ff<=capacity)
        p=input[idx].ss+knapsack(idx+1,w+input[idx].ff);
    else if(w+input[idx].ff>capacity)
    {
        if((w+input[idx].ff>2000) && (w+input[idx].ff<=capacity+200) && !test)
        {
            test=1;
            capacity+=200;
            p=input[idx].ss+knapsack(idx+1,w+input[idx].ff);
            test=0;
            capacity-=200;
        }
    }
    q=knapsack(idx+1,w);

    return ret=max(p,q);
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    while(cin>>capacity>>n)
    {
        z++;

        loop(i,n) cin>>input[i].ff>>input[i].ss;
        test=0;
        sort(input,input+n);
        cout<<knapsack(0,0)<<endl;

    }
    return 0;
}