PAT 甲级 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

题意：给169(N)作因式分解，分解成5(K)项,每个因式可以选多次，最后输出选择的因式的2(p)次方（递减顺序，且要保证该序列的序列和是所有解里面最大的）

n,p,k依据题目输入

思路：联想到完全背包问题，即一个物品可以被选择多次，每个物品有选和不选两种情况，所以就有项数联想到背包物品，数n联想到背包容量，序列和最大联想到背包最大价值，因此可以写出完全背包的深度优先搜索模型

//因为是先选，嵌套一次就选一次，这样就可以体现出完全背包问题了;
temp.push_back( );//先选;
DFS(index,sum,facsum);//选择的情况;
temp.pop_back( )//选择的情况结束;
DFS(index-1,sum,facsum);//这一项不选，进入下一项的判断;

代码：
 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,k,p;//数，有n项数，p次方; 
int maxfac=-1;//用于判断是否有最优解，最优解是什么; 
vector<int > fac,temp,ans;//放置预处理的平方和，临时的答案序列，最终的答案序列; 
int power(int x){//算数的p次方; 
	int ans=1;
	for(int i=0;i<p;i++){
		ans*=x;//求x的p次方,乘多少次就是多少次方嘛； 
	}
	return ans; 
}
void deal( ){//预处理平方和到fac里面; 
	int temp=0,i=0;
	while(temp<=n){
		fac.push_back(temp); 
		temp=power(++i);
	}
}
//当前处理到index项，现在已选入nowk个数，此时的选的数的p次方的和，因式和（用于判断该解的因式是不是最大的）； 
void DFS(int index,int nowk,int sum,int sumfac){
	if(sum==n&&nowk==k){//进来先判断临界条件; 
		if(maxfac<sumfac){//目前是最优序列; 
			ans=temp;//vector数组可以直接替换;
			maxfac=sumfac;//更新最大值; 
		}
		return ;
	}
	if(sum>n||nowk>k)return ;//修叶； 
		if(index-1>=0){//fas[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( );//预处理，将各项的p次方算出来; 	
	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;	
}

无注释代码：
 

#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;	
}