Ciel and Receipt Problem Code: CIELRCPT

1

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) {
// your code goes here
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;

}

2

Firstly, please Format your code.

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.

3

Thank you very much. I got your answer.

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?

4

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]=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
5

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