OJ Board

Code: Select all

2
6
71 6
41 3
53 8
93 11
26 22
24 11
2
29
26
8
61 5
99 11
71 30
77 15
93 7
56 4
37 2
8 6
2
4
16

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define CASES 10000

int main(){
   int caseno;
   int n,p,w,g,mw;
   int i;
   
   printf("%d\n",CASES);
   for(caseno=1;caseno<=CASES;caseno++){
      n=1+rand()%10;
      printf("%d\n",n);
      for(i=0;i<n;i++){
         p=1+rand()%100;
         w=1+rand()%30;
         printf("%d %d\n",p,w);
         }
      g=1+rand()%5;
      printf("%d\n",g);
      for(i=0;i<g;i++){
         mw=1+rand()%30;
         printf("%d\n",mw);
         }
      }
   return 0;
   }

Code: Select all

#include <stdio.h>

#define NUM 1001
#define GROUP 101
#define MW 31


int max( int x, int y )
{
	return (x > y) ? x : y;
}


int dp_knapsack( const int *p, const int *wi, const int num, const int maxw )
{
	int carry[NUM][MW], i, w;

	for( i = 0; i <= num; i++ )
		carry[i][0] = 0;
	for( w = 0; w <= maxw; w++ )
		carry[0][w] = 0;

	for( i = 1; i <= num; i++ )
		for( w = 1; w <= maxw; w++ )
			{
				if( wi[i] >= w )
					carry[i][w] = carry[i-1][w];
				else
					carry[i][w] = max( carry[i-1][w], carry[i-1][w-wi[i]] + p[i] );
			}

	printf( "%d\n", carry[num][maxw] );

	return carry[num][maxw];
}

	


int main()
{
	int no, ng, tcases, i, total;
	int price[NUM], weight[NUM], maxw;

	scanf( "%d", &tcases );
	while( tcases-- )
		{
			total = 0;
			scanf( "%d", &no );

			for( i = 0; i < no; i++ )
				scanf( "%d %d", &price[i], &weight[i] ); 

			scanf( "%d", &ng ); 
			for( i = 0; i < ng; i++ )
				{
					scanf( "%d", &maxw ); 
					total += dp_knapsack( price, weight, no, maxw );
				}
			printf( "total: %d\n", total );
		}

	return 0;
}			

Code: Select all

#include <stdio.h>

#define NUM 1001
#define GROUP 101
#define MW 31

int carry[NUM][MW];
int p[NUM], wi[NUM];

int max( int x, int y )
{
   return (x > y) ? x : y;
}


void dp_knapsack(int num)
{
   int  i, w;

   for( i = 0; i <= num; i++ )
      carry[i][0] = 0;
   for( w = 0; w < MW; w++ )
      carry[0][w] = 0;

   for( i = 1; i <= num; i++ )
      for( w = 1; w < MW; w++ )
         {
            if( wi[i] > w )
               carry[i][w] = carry[i-1][w];
            else
               carry[i][w] = max( carry[i-1][w], carry[i-1][w-wi[i]] + p[i] );
         }
}

   


int main()
{
   int no, ng, tcases, i, total;
   int  maxw;

   scanf( "%d", &tcases );
   while( tcases-- )
      {
         total = 0;
         scanf( "%d", &no );

         for( i = 1; i <= no; i++ )
            scanf( "%d %d", &p[i], &wi[i] );

		 dp_knapsack(no);
         scanf( "%d", &ng );
         for( i = 0; i < ng; i++ )
            {
               scanf( "%d", &maxw );
               total += carry[no][maxw];
            }
         printf( "%d\n", total );
      }

   return 0;
}          

Code: Select all

int best(int w, int i1) {
	int t = 0;
	if(cache[w][i1] != -1) return cache[w][i1];
	for(int i = i1; i < 1000; i++) {
		if(o1[i] == -1) break;
		if( (w-o2[i]) >= 0) {
			t = max( best(w-o2[i], i+1)+o1[i], t);
		}
		
	}
	cache[w][i1]=t;
	return t;
}

Code: Select all

#include<stdio.h>
#define max 10100
long m[max][100],N,W[max],V[max];
void knapsack(){
	int i,w;
	for(i=0;i<=N;i++)m[i][0]=0;
	for(i=0;i<=35;i++)m[0][i]=0;
	for(i=1;i<=35;i++){
		for(w=1;w<=35;w++){
			if(w<W[i])m[i][w]=m[i-1][w];
			else{
				if(m[i-1][w]>=V[i]+m[i-1][w-W[i]])m[i][w]=m[i-1][w];
				else m[i][w]=V[i]+m[i-1][w-W[i]];
			}
		}
	}
}
int main(){
	int i,num,T,person,amount;
	//freopen("10130.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d",&N);
		for(i=1;i<=N;i++)scanf("%d%d",&V[i],&W[i]);
		knapsack();
		scanf("%d",&num);
		amount=0;
		while(num--){
			scanf("%d",&person);
			amount+=m[N][person];
		}
		printf("%d\n",amount);
	}
	return 0;
}

Code: Select all

Removed.

Code: Select all

   if(memo[n][wa]!=-1)return memo[n][wa];
   if(n<0 || wa<=0)return 0;