10819 - Trouble of 13-Dots

sclo · Post by **sclo** » Fri Sep 08, 2006 2:42 am

I don't understand why you are doing it this way, and why you need to sort.
It is sufficient to define a table F such that F[j] is the max sum of favor of items taken from 0 to i where their total price is j.

nymo · Post by **nymo** » Wed Nov 22, 2006 6:04 pm

Hi, I 've tried all test cases posted on all the threads of this problem and get correct answer. But I am getting WAs[... several times ]

Can someone post some test cases? please. Thanks.

nymo · Post by **nymo** » Thu Nov 23, 2006 8:24 pm

I get ACC now, I change the implementation and recode it. Thanks.

mhayter1 · Post by **mhayter1** » Mon Aug 06, 2007 12:27 am

Hi! I've modified my code and I pass all the test cases given on the forums. I submit my code but it gets WA. Could someone please help me? Here's my code:

Code: Select all

#include<iostream>
using namespace std;

struct item
{
    int cost;
    int findex;
};

const int NITEMS=110;
const int MAXSUM=10210;
item items[NITEMS];

int main()
{
    int money,nitems;
    while(cin>>money>>nitems)
    {
        int sums[MAXSUM]={0};
        for(int i=0;i<nitems;i++)
        {
            cin>>items[i].cost>>items[i].findex;
        }
        //credit card refund possible
        int omoney=money;
        if(money>1800)
            money+=200;
        sums[items[0].cost]=items[0].findex;
        for(int i=1;i<nitems;i++)
        {
            int cost=items[i].cost;
            int findex=items[i].findex;
            for(int j=money-cost;j>=0;j--)
            {
                if(sums[j]!=0)
                {
                   if(sums[j]+findex>sums[j+cost])
                   {
                       sums[j+cost]=sums[j]+findex;
                   }
                }
            }
            if(sums[cost]==0 || sums[cost]<findex)
            {
                sums[cost]=findex;
            }
        }
        int mxfavour=0;
        //finds max favour considering refund
        for(int i=0;i<=money;i++)
        {
            if(i<=omoney || i>2000)
                if(sums[i]>mxfavour)mxfavour=sums[i];
        }
        cout<<mxfavour<<endl;
    }
    return 0;
}

MRH · Post by **MRH** » Tue Oct 06, 2009 6:42 pm

WHY THIS CASE OUTPUT IS: 2
1900 3
2000 5
1950 1
101 1

PLEASE EXPLAIN & CLEAR ME

MY CODE GIVE : 5

zeeshan07 · Post by **zeeshan07** » Wed Jun 30, 2010 2:26 pm

can someone please tell me where i'm wrong???
thanx...

Code: Select all

#include<iostream>

using namespace std;

int a[105][10005];


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



int main()
{
	int w[200],p[200],n,M,i,j,t;
	



	while(scanf("%d %d",&M,&n)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d %d",&w[i],&p[i]);


		memset(a,0,sizeof(a));

		if(M>1800)
			M+=200;

		for(i=1;i<=n;i++)
		{
			for(j=1;j<=M;j++)
			{
				if(j<w[i])
					a[i][j]=a[i-1][j];
				else
					a[i][j]=MAXX(p[i]+a[i-1][j-w[i]],a[i-1][j]);

			}
		}


		printf("%d\n",a[n][M]);
		
	}
	return 0;

}

suneast · Post by **suneast** » Fri Dec 31, 2010 8:49 am

hi, all :
here's my solution:

Code: Select all

@ make Money = m+200, whatever the exact value of m is
@ do 0-1 knapsack
@ for (0 - > Money)
     if MoneySpend>2000 || MoneySpend <= m
		ChkMin(ans)

Hope I'm help: )

sijan · Post by **sijan** » Thu Jan 31, 2013 10:57 pm

I am getting WA. Whats the problem ???

Code: Select all


//////////////////////////////////////////
//   Bismillahir Rahmanir Rahim        //
//   Author      : Shohan Ahmed Sijan //
//   Country     : Bangladesh        //
//   Algorithm   :DP
//   Complexity  :%
//   University  : East West University //
/////////////////////////////////////////
#pragma warning(disable:4786)
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

#define Re(i,n) for(i=0;i<n;i++)
#define inf 999999999
#define PI acos(-1)
#define EPS 1e-12
#define sqrt(x) sqrt(abs(x))
#define M 10900

typedef  int I;

I Max(I a,I b)
{
	return a>b?a:b;
}

I amount,num,dp[109][M],m2,p2,save[M];
struct st
{
	int price,fob;
}item[110];
I call(I posi,I money, I f)
{
	save[money]=Max(f,save[money]);
	if(posi==num)return 0;
	if(dp[posi][money]!=-1)return dp[posi][money];
	I mx=call(posi+1,money,f);
	if(item[posi].price+money<=amount)
	{
		mx=Max(mx,call(posi+1,money+item[posi].price,f+item[posi].fob) + item[posi].fob );
	}
	return dp[posi][money]=mx;
}
int main()
{
	I i,cas=1,j;

	while(scanf("%d %d",&amount,&num)!=EOF)
	{
		for(i=0;i<num;i++)
			scanf("%d %d",&item[i].price,&item[i].fob);
		memset(dp,-1,sizeof dp);
		if(amount>2000)amount+=200;
		else if(amount>1800)
		{
			amount+=200;
			memset(save,-1,sizeof save);
			p2=0;
			call(0,0,0);
			for(i=amount;i>2000;i--)
					if(save[i]>p2)
					{
						p2=save[i];
					}
			for(i=amount-200;i>=0;i--)
					if(save[i]>p2)
					{
						p2=save[i];
					}
			printf("%d\n",p2);
			continue;
		}
		printf("%d\n",call(0,0,0));
	}

	return 0;
}

brianfry713 · Post by **brianfry713** » Fri Feb 01, 2013 10:07 pm

Input:

Code: Select all

AC output: 31

raj · Post by **raj** » Mon Sep 02, 2013 7:16 am

Need Help!!!!!!!!!! facing ""Run Time Error""...............

Code: Select all

removed

brianfry713 · Post by **brianfry713** » Tue Sep 03, 2013 9:58 pm

Try input:

Code: Select all

raj · Post by **raj** » Thu Sep 12, 2013 12:10 am

Need help i am getting ""WRONG ANSWER""

Code: Select all

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException {
        // TODO Auto-generated method stub
        BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader k = new BufferedReader(new FileReader("D:/Uva-input.txt.txt"));
        PrintWriter z = new PrintWriter(System.out);
        //BufferedWriter z = new BufferedWriter(new OutputStreamWriter(System.out));
        String line;
        while((line = k.readLine())!=null){
        	StringTokenizer s = new StringTokenizer(line);
        	int max = Integer.valueOf(s.nextToken());
        	if(max>2000) max = max + 200;
        	int items = Integer.valueOf(s.nextToken());
            int [] cost = new int[items+1];
            int [] weight = new int[items+1];
            int [][] dp = new int[items+1][10000+1+201];
            int c = 1;
            int nn = items;
            while(nn-->0){
                StringTokenizer ss = new StringTokenizer(k.readLine());
                weight[c] = Integer.valueOf(ss.nextToken());
                cost[c] = Integer.valueOf(ss.nextToken());
                c++;
            }
            for(int i = 1;i<=items;i++){
				for(int w = 1;w<=max;w++){
					if(w>=weight[i]){
						dp[i][w] = Math.max(cost[i]+dp[i-1][w-weight[i]],dp[i-1][w]);
					}
					else{
						dp[i][w] = dp[i-1][w];
					}
				}
			}
            z.println(dp[items][max]);
        }
        z.flush();
    } 
}

brianfry713 · Post by **brianfry713** » Fri Sep 13, 2013 12:14 am

Input:

Code: Select all

AC output:

Code: Select all

mratan16 · Post by **mratan16** » Sun Jul 20, 2014 12:31 pm

I cannot seem to figure out why it fails on test case:
1801 3

Code: Select all

901 2
901 2
200 1

Can anyone help?

Code: Select all

Removed

brianfry713 · Post by **brianfry713** » Tue Jul 22, 2014 9:40 pm

Your code has a number of problems. Your keep array is filling up beyond the amount you spent. On that input, one way to solve it would be to set keep[1][901] equal to 2 but keep[1][902] could equal 0 because you didn't actually spend 902 dollars. You could also try input:

Code: Select all

1801 1
1802 1

OJ Board

10819 - Trouble of 13-Dots

Some test cases please ...

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots

Re: 10819 - Trouble of 13-Dots