OJ Board

Code: Select all

Removed after AC . Codes were fine.There was an online judge problem . Now it's solved and all the solutions are accepted

Code: Select all

AC

Code: Select all

#include <stdio.h>
#include <string.h>
#include <vector>

#define MAX 21

using namespace std;

unsigned int n, n_tracks, i, u, k;
int max_result;
int tracks[MAX];
int used[MAX];
vector<int> answer;
vector<int> current_list;

int max(int a, int b)
{
  return a > b ? a : b;
}

int get_maximum_tracks(int j, int current_max)
{
  used[j] = 1;
  current_max += tracks[j];

  if (current_max > n)
  {
    return -1;
  }

  if (current_max > max_result)
  {
    answer.clear();

    for (k = 0; k < (int) current_list.size(); k++)
    {
      answer.push_back(current_list[k]);
    }

    max_result = current_max;
  }

  for (u = 0; u < n_tracks; u++)
  {
    if (!used[u] && u != j)
    {
      current_list.push_back(u);
      get_maximum_tracks(u, current_max);
      current_list.pop_back();
    }
  }

  return current_max;
}

int main()
{
  while (scanf("%d %d", &n, &n_tracks) != EOF)
  {
    memset(tracks, 0, sizeof tracks);
    current_list.clear();
    max_result = -1;

    for (i = 0; i < n_tracks; i++)
    {
      scanf("%d", &tracks[i]);
    }

    /* Program Logic */
    for (i = 0; i < n_tracks; i++)
    {
      memset(used, 0, sizeof used);
      current_list.push_back(i);
      get_maximum_tracks(i, 0);
      current_list.pop_back();
    }

    for (i = 0; i < (int) answer.size(); i++)
    {
      printf("%d ", tracks[answer[i]]);
    }

    printf("sum:%d\n", max_result);
  }

  return 0;
}

Code: Select all

4 1 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45

Code: Select all

1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45

Code: Select all

#include<stdio.h>
#include<string.h>
int d[250][150005],a[250],s[250],t,n,i,j;
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		scanf("%d",&t);
		for(i=1;i<=t;i++)
			scanf("%d",&a[i]);
		memset(d,0,sizeof(d));
		memset(s,0,sizeof(s));

		for(i=1;i<=t;i++)
			for(j=0;j<=n;j++)
				if(j<a[i])
					d[i][j]=d[i-1][j];
				else
					d[i][j]=(d[i-1][j]>(d[i-1][j-a[i]]+a[i]))?d[i-1][j]:(d[i-1][j-a[i]]+a[i]);

		for(i=t,j=n;i>=1&&j>0;i--)
			if(d[i][j]==(d[i-1][j-a[i]]+a[i]))
			{
				s[i]=1;j-=a[i];
			}

			for(i=1;i<=t;i++)
				if(s[i])
					printf("%d ",a[i]);
			printf("sum:%d\n",d[t][n]);
	}
	return 0;
}

Code: Select all

Got AC using brute force method. Thanks brianfry.

Code: Select all

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define pb push_back
using namespace std;

typedef vector<int> vi;

int main ()
{
	int n;
	while ((scanf ("%d", &n)) != EOF)
	{
		int tracks;
		scanf ("%d", &tracks);
		int a[tracks];
		for (int i = 0; i < tracks; ++i)
			scanf ("%d", &a[i]);
		int lim = (int) pow(2, tracks);
		int ans = 0;
		vi track;
		for (int i = 1; i <= lim; ++i)
		{
			int temp = i;
			int sum = 0;
			vi temp_list;
			for (int j = 0; j < tracks; ++j)
			{
				if (temp & (1<<j))
				{
					sum += a[j], temp_list.pb(a[j]);
				}	
			}		
			if (sum <= n && sum > ans)
				ans = sum, track = temp_list;		
		}
		for (int i = 0; i < track.size(); ++i)
			printf ("%d ", track[i]);
		printf ("sum:%d\n", ans);	
	}
	return 0;
}	

Code: Select all

/*
 Problem name :
 Algorithm : Not Sure Yet
 Contest/Practice :
 Source :
 Comment : Whenever you start to believe  yourself, people also start to believe in you
 Date : --
 Last Update : 23-Dec-2014
*/

#include<bits/stdc++.h>

#define pause           system("pause");
#define FOR(s,e,inc)    for(int i=s;i<=e;i+=inc)
#define mod             1000000007
#define inf             1<<30
#define pb              push_back
#define ppb             pop_back
#define mp              make_pair
#define F               first
#define S               second
#define sz(x)           ((int)x.size())
#define sqr(x)          ( (x)* (x) )
#define eps             1e-9
#define gcd(x,y)         __gcd(x,y)
#define lcm(x,y)        (x/gcd(x,y))*y
#define on(x,w)         x|(1<<w)
#define check(x,w)      (x&(1<<w))
#define all(x)          (x).begin(),(x).end()
#define pf              printf
#define pi              acos(-1.0)
#define reset(x,v)      memset(x,v,sizeof(x));
#define AND             &&
#define OR              ||

typedef long long ll;
typedef unsigned long long llu;

using namespace std;


template<class T>
inline T mod_v(T num)
{
    if(num>=0)
        return num%mod;
    else
        return (num%mod+mod)%mod;
}

template<class T>
T fast_pow(T n , T p)
{
    if(p==0) return 1;
    if(p%2)
    {
        T g=mod_v ( mod_v(n) * mod_v(fast_pow(n,p-1)) );
        return g;
    }
    else
    {
        T g=fast_pow(n,p/2);
        g=mod_v( mod_v(g) * mod_v(g) ) ;
        return g;
    }
}

template<class T>
inline T modInverse(T n)
{
    return fast_pow(n,mod-2);
}

template<class T>
inline void debug(string S1,T S2,string S3)
{
    cout<<S1<<S2<<S3;
}

template<class T>
inline T in()
{
    register char c=0;
    register T num=0;
    bool n=false;
    while(c<33)c=getchar();
    while(c>33){
        if(c=='-')
            n=true;
        else num=num*10+c-'0';
        c=getchar();
    }
    return n?-num:num;
}

#ifndef ONLINE_JUDGE
#  define p(x) cout<<x<<endl;
#else if
#  define p(x) 0;
#endif

/*...... ! Code start from here ! ......*/

int dp[25][5000] ;
int ok[25][5000]={0} ;
int track[25];

int cc;
int n,t;

int re(int i,int sum)
{
    if(i==t)
    {
        if(sum<=n) return sum;
        else return -inf;
    }

    if(ok[i][sum]==cc) return dp[i][sum];



    dp[i][sum]=-inf;

    dp[i][sum]=max(dp[i][sum], re(i+1,sum+track[i] ));
    dp[i][sum]=max(dp[i][sum], re(i+1,sum ));
    ok[i][sum]=cc;

    return dp[i][sum];
}



void print_path(int i,int sum,int st)
{//printf("%d %d %d\n",i,sum,st);
    if(i==t || st==sum)
    {
        return;
    }

    if(sum==re(i+1,st+track[i]) )
    {
        printf("%d ",track[i]);
//        ans.pb(track[i] );
        print_path(i+1,sum,st+track[i]);
        return;
    }
    else
    {
        print_path(i+1,sum,st);
        return;
    }
}


int main()
{
    #ifndef ONLINE_JUDGE
        freopen ( "in.txt", "r", stdin );
    #endif

    cc=1;

    while(scanf("%d %d",&n,&t)==2)
    {
        int res;
        for(int i=0;i<t;i++)
        {
            scanf("%d",&track[i]);
        }

        res=re(0,0);
        print_path(0,res,0);

        printf("sum:%d\n",res);

        cc++;
    }

    return 0;
}