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
Moderator: Board moderators
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
Yeah, I've realized that, but I have no idea of how to oredr them like in the input. I'm asking for help with this part.brianfry713 wrote:Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD
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;
}