Pat grade a 1103 integer factorizatio

The K−P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K and P.

Input Specification:

Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P (1<P≤7). The numbers in a line are separated by a space.

Output Specification:

For each case, if the solution exists, output in the format:

N = n[1]^P + ... n[K]^P

where n[i] (i = 1, ..., K) is the i-th factor. All the factors must be printed in non-increasing order.

Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122+42+22+22+12, or 112+62+22+22+22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen -- sequence { a1​,a2​,⋯,aK​ } is said to be larger than { b1​,b2​,⋯,bK​ } if there exists 1≤L≤K such that ai​=bi​ for i<L and aL​>bL​.

If there is no solution, simple output Impossible.

Sample Input 1:

169 5 2

Sample Output 1:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

Sample Input 2:

169 167 3

Sample Output 2:

Impossible

The question ： to 169(N) Factorization , Decompose into 5(K) term , Each factor can be chosen many times , Finally, output the selected factor 2(p) Power （ Descending order , And ensure that the sequence sum of the sequence is the largest of all solutions ）

n,p,k Input according to the topic

Ideas ： Think of the complete knapsack problem , That is, an item can be selected many times , Each item can be selected or not , So there are items associated with backpack items , Count n Think of backpack capacity , Sequence and maximum associative knapsack maximum value , Therefore, we can write a full knapsack depth first search model

// Because it is the first choice , Nest once and choose once , This can reflect the complete knapsack problem ;
temp.push_back( );// Choose... First ;
DFS(index,sum,facsum);// The situation of choice ;
temp.pop_back( )// The selected situation ends ;
DFS(index-1,sum,facsum);// Don't choose this one , Go to the next judgment ;

Code ：
 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,k,p;// Count , Yes n Number of items ,p Power ; 
int maxfac=-1;// Used to judge whether there is an optimal solution , What is the optimal solution ; 
vector<int > fac,temp,ans;// Place the sum of squares of the pretreatment , Temporary answer sequence , The final answer sequence ; 
int power(int x){// Count p Power ; 
	int ans=1;
	for(int i=0;i<p;i++){
		ans*=x;// seek x Of p Power , How many times is how many times ; 
	}
	return ans; 
}
void deal( ){// Preprocess the sum of squares to fac Inside ; 
	int temp=0,i=0;
	while(temp<=n){
		fac.push_back(temp); 
		temp=power(++i);
	}
}
// Currently processed to index term , Now selected nowk Number , At this time, the number of choices p The sum of powers , Factor and （ The factor used to judge whether the solution is the largest ）; 
void DFS(int index,int nowk,int sum,int sumfac){
	if(sum==n&&nowk==k){// First judge the critical condition ; 
		if(maxfac<sumfac){// At present, it is the optimal sequence ; 
			ans=temp;//vector Arrays can be directly replaced ;
			maxfac=sumfac;// Update Max ; 
		}
		return ;
	}
	if(sum>n||nowk>k)return ;// Pruning leaves ; 
		if(index-1>=0){//fas[0] No choice ; 
		temp.push_back(index);// Choose... First ; 
		DFS(index,nowk+1,sum+fac[index],sumfac+index);// Choose it and see if you can choose ;
		temp.pop_back();// You can't choose again or don't choose if you don't meet the conditions ;
		DFS(index-1,nowk,sum,sumfac);// Enter other branches to judge ; 
	}
}

int main( ){
	scanf("%d %d %d",&n,&k,&p);
	deal( );// Preprocessing , The of each item p To the power of ; 	
	DFS(fac.size()-1,0,0,0);// Don't forget to use depth first search to find the best solution , That is, don't forget to call the function ; 
	if(maxfac==-1) printf("Impossible");
	else
	for(int i=0;i<ans.size();i++) i==0?printf("%d = %d^%d",n,ans[i],p):printf(" + %d^%d",ans[i],p);	
	return 0;	
}

Uncommented code ：
 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,k,p;
int maxfac=-1; 
vector<int > fac,temp,ans;
int power(int x){
	int ans=1;
	for(int i=0;i<p;i++){
		ans*=x;
	}
	return ans; 
}
void deal( ){ 
	int temp=0,i=0;
	while(temp<=n){
		fac.push_back(temp); 
		temp=power(++i);
	}
}
void DFS(int index,int nowk,int sum,int sumfac){
	if(sum==n&&nowk==k){
		if(maxfac<sumfac){ 
			ans=temp;
			maxfac=sumfac;
		}
		return ;
	}
	if(sum>n||nowk>k)return ; 
		if(index-1>=0){
		temp.push_back(index);
		DFS(index,nowk+1,sum+fac[index],sumfac+index);
		temp.pop_back();
		DFS(index-1,nowk,sum,sumfac);
	}
}

int main( ){
	scanf("%d %d %d",&n,&k,&p);
	deal( ); 	
	DFS(fac.size()-1,0,0,0); 
	if(maxfac==-1) printf("Impossible");
	else
	for(int i=0;i<ans.size();i++) i==0?printf("%d = %d^%d",n,ans[i],p):printf(" + %d^%d",ans[i],p);	
	return 0;	
}