abhayg271
BAN USERThis is a modification of the knapsack problem (check wiki). The maximum weight the knapsack can hold is the number of operations. The weights are assigned to be one (as they take one operation) and the values are the numbers itself (2 to 9). There is an additional constraint to the maximum value('limit' variable in my program, limit=10^N-1) , which is decided by the number of digits the calculator can display. I had written a program for the knapsack problem earlier, which I have modified to suit this problem. Another subtle difference is that the value (2 to 9) is multiplied to the max value instead of being added as in the case of the knapsack problem. The program is quite fast for a variety of inputs. Additional checks can be added to optimize the program, as when the O<=N (number of operations<= number of digits), then the output should always be 9^O, and there is no need to call the recursive function at all!(verify), which I have not implemented. Hope this solution helps. Enjoy!
#include<iostream>
using namespace std;
int directi(int w,int itemw[], int itemv[],int noi,int limit)
{
int temp=1,temp1=1;
for(int i=0;i<noi;i++)
{
if(w>=itemw[i])
{
temp1=directi(w-itemw[i],itemw,itemv,noi,limit/itemv[i]);
if(temp1*itemv[i]>temp&& temp1*itemv[i]<=limit)
temp=temp1*itemv[i];
}
}
return temp;
}
int main()
{
int itemw[10];int itemv[10];
int w; int noi;int limit;
cout<<"enter the max no of operations: ";//cout<<"enter the knapsack capacity: ";
cin>>w;
//cout<<"enter the no of items: ";
noi=8;//cin>>noi;
cout<<"enter the limit: ";
cin>>limit;
for(int i=0;i<noi;i++)
{
//cout<<"\nenter item weight: ";
itemw[i]=1;//cin>>itemw[i];
//cout<<"\nenter item value: ";
itemv[i]=i+2;//cin>>itemv[i];
}
cout<<"The maximum value is: "<<directi(w,itemw,itemv,noi,limit)<<"\n";
system("pause");
return 0;
}
This is a modification of the knapsack problem (check wiki). The maximum weight the knapsack can hold is the number of operations. The weights are assigned to be one (as they take one operation) and the values are the numbers itself (2 to 9). There is an additional constraint to the maximum value('limit' variable in my program, limit=10^N-1) , which is decided by the number of digits the calculator can display. I had written a program for the knapsack problem earlier, which I have modified to suit this problem. Another subtle difference is that the value (2 to 9) is multiplied to the max value instead of being added as in the case of the knapsack problem. The program is quite fast for a variety of inputs. Additional checks can be added to optimize the program, as when the O<=N (number of operations<= number of digits), then the output should always be 9^O, and there is no need to call the recursive function at all!(verify), which I have not implemented. Hope this solution helps. Enjoy!
- abhayg271 December 01, 2013