tag:blogger.com,1999:blog-7342229757832365594.post1747532573428193059..comments2023-04-28T04:10:43.605-07:00Comments on HINTS AND SOLUTION TO SPOJ QUESTIONS: ABA12CSushanthttp://www.blogger.com/profile/14186565366407945495noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-7342229757832365594.post-12948230418417400982020-04-21T05:23:06.281-07:002020-04-21T05:23:06.281-07:00How does that mean we have not found the answer ye...How does that mean we have not found the answer yet?Anonymoushttps://www.blogger.com/profile/01057667888094834263noreply@blogger.comtag:blogger.com,1999:blog-7342229757832365594.post-30585690777091090742019-02-14T17:54:27.372-08:002019-02-14T17:54:27.372-08:00In your code, you write: ans[i] = min(ans[i], ans[...In your code, you write: ans[i] = min(ans[i], ans[j] + p[i-j]);<br />I think it must be ans[i]=min(ans[i],ans[i-j]+p[j]);<br />Although Both of them can be true, I think the second one is more comfortable.Hd7https://www.blogger.com/profile/09575896852639433257noreply@blogger.comtag:blogger.com,1999:blog-7342229757832365594.post-78838725818121019412017-01-28T12:29:47.210-08:002017-01-28T12:29:47.210-08:00p[ i ] denotes the price of i kg apples. So as per...p[ i ] denotes the price of i kg apples. So as per the question p[i] can be equal to -1. ans[i] denotes the minimum to cost to buy i kg of apples. If ans[j] = -1, then that means that for the following j we have not found the answer yet. So in either of the cases let the for loop continue.Sushanthttps://www.blogger.com/profile/14186565366407945495noreply@blogger.comtag:blogger.com,1999:blog-7342229757832365594.post-41078809576109304192017-01-04T00:09:26.780-08:002017-01-04T00:09:26.780-08:00can you explain the line----->
if(p[i-j] == -1...can you explain the line-----><br /> if(p[i-j] == -1 || ans[j] == -1)<br /> continue;Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7342229757832365594.post-33672456157255000532016-06-29T00:33:06.456-07:002016-06-29T00:33:06.456-07:00Yeah, I think the complexity should be O(k*k*n) al...Yeah, I think the complexity should be O(k*k*n) although I have not tried it yet.Sushanthttps://www.blogger.com/profile/14186565366407945495noreply@blogger.comtag:blogger.com,1999:blog-7342229757832365594.post-58148328798650254582016-06-13T05:25:09.569-07:002016-06-13T05:25:09.569-07:00This means that, for eg if I need to buy apples of...This means that, for eg if I need to buy apples of weight 5kg, then to find ans[5] I have several options like buy 5 packets of 1 kg or buy 1 packet of 2kg and 1 of 3kg etc. <br />Hence in order to find the best case, I run a loop from (i =0 to i<j) and find the combination which costs the minimum. So ans[j] will be minimum of either ans[j] , i.e, I do not choose the ith packet, or ans[j-i] + price[i], i.e, I have chosen the ith packet. <br />For further reading on unbounded knapsack, you can refer this site :<br />http://www.csegeek.com/csegeek/view/tutorials/algorithms/dynamic_prog/dp_part7.phpSushanthttps://www.blogger.com/profile/14186565366407945495noreply@blogger.comtag:blogger.com,1999:blog-7342229757832365594.post-41753506884074806902016-06-13T01:59:35.372-07:002016-06-13T01:59:35.372-07:00Okay the complexity of this solution is K^2 right?...Okay the complexity of this solution is K^2 right? In case we consider n, it will increase to O((K^2)*N) right?tanmay kulshresthahttps://www.blogger.com/profile/10112640673754333644noreply@blogger.comtag:blogger.com,1999:blog-7342229757832365594.post-79792215673986393462016-06-12T23:14:14.310-07:002016-06-12T23:14:14.310-07:00Read the comments in the question. Many users have...Read the comments in the question. Many users have written that if they considered 'n' then they got a WA but without considering it their solution got AC.<br />Hence, even I did not consider it.Sushanthttps://www.blogger.com/profile/14186565366407945495noreply@blogger.comtag:blogger.com,1999:blog-7342229757832365594.post-16754165166626225482016-06-11T23:34:01.658-07:002016-06-11T23:34:01.658-07:00its wrong sol...u r not considering n anywhere whi...its wrong sol...u r not considering n anywhere which is the max amt of packets u can buy<br />for test case : 1 5 1 3 4 5 6 the ans should be 6 but ur code is giving 5.Anonymoushttps://www.blogger.com/profile/08668781233383351275noreply@blogger.comtag:blogger.com,1999:blog-7342229757832365594.post-7546910975349876042016-06-03T02:55:17.294-07:002016-06-03T02:55:17.294-07:00can you explain this line-- ans[ j ] = minimum[ an...can you explain this line-- ans[ j ] = minimum[ ans[j - i] + price[ i ] ] for i= 0,1....j-1.Anonymoushttps://www.blogger.com/profile/05988801209565538765noreply@blogger.com