 # Ciel and Receipt Problem Code: CIELRCPT

Is there any algorithm for this problem? because I am trying to code as per the problem.
I know below code is wrong and not efficient. please help me if any algorithm is there behind this.
myCode:
#include <stdio.h>
#include<math.h>
int main(void) {
int n,t;
scanf("%d",&n);
while(n–){
int count=0,count1,sum=0,price,j=0,finalCount;
scanf("%d",&t);
for(int i=pow(2,j);j<=12;i=pow(2,++j)){
while(price<=t){

``````           while(1){
sum=sum+i;
count++;
if(sum>=t){
price=sum;
sum = 0;
count1=count;
count=0;
break;
}
}
}
if(price == t){
if(count1<count){
finalCount = count1;
}else if(count1>count){
finalCount = count;
}
}
}
}
// printf("%d\n",finalCount);
}
return 0;
``````

}

Secondly, to solve it, Notice that it is always better to take the largest one possible, as the only other way is to get at least 2 of the smaller ones instead, which is worse.

This is only correct because they are powers of 2, this does not apply to random numbers.

So our main algorithm is pretty simple.

``````    int n;
cin>>n;
int s=2048;
int ans=0;
while(n>0){
ans+=n/s;
n%=s;
s/=2;
}
cout<<ans<<"\n";
``````

We start with the largest possible. We count what is the maximum we can take, which is \lfloor n/s\rfloor . n becomes n\%s, because only the remainder will be left over. Then we check for the next smallest.

Lastly, use `pow` only for floating point calculations. It’s not trustworthy.

I may be wrote code like straight forward to the question.

I have iterated loop from 2 to 2048 and calculated the sum and checked if it is equal or not…

please clarify me one thing. thank you once again.

Is there any algorithm used for this problem like knapsack?

You don’t need a knapsack dp, but you can use it here

Let dp[i] be the least amount of dishes to spend i rupees. Then dp[i]=min(dp[i-price]+1) for all prices in the menu. Just compute the answers from 0 to p.

``````    int n;
cin>>n;
vector<int> dishprices;
for(int i=1;i<=2048;i*=2){
dishprices.push_back(i);//First put all the prices in a vector
}
vector<int> dp(n+1, 1e9);//Set dp to infinity initially
dp=0;//We need 0 dishes to spend 0
for(int i=1;i<=n;i++){//Iterate through all p
for(const auto &price : dishprices){//Go through all the dishes
if(i>=price){//If it is possible to buy this dish
dp[i]=min(dp[i], dp[i-price]+1);//Take minimum
}
}
}
cout<<dp[n]<<"\n";//Minimum for price n
``````

Thank you very much for your help. I got it.