PAT A1103 Integer Factorization (30 分)

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 12?2??+4?2??+2?2??+2?2??+1?2??, or 11?2??+6?2??+2?2??+2?2??+2?2??, 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 { a?1??,a?2??,?,a?K?? } is said to be larger than { b?1??,b?2??,?,b?K?? } if there exists 1≤L≤K such that a?i??=b?i?? for i<L and a?L??>b?L??.

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

实现思路：
这题是一道很好的题，对于这题的dfs写法我也采用了两种方式，而且最终两种方法的时间效率差不多都在200ms多（最佳情况下），这里有几个细节点，优先将每个数i的次方值存入一个数组，如果在递归时候每次调用pow函数计算次方值，会使得算法整体时间多了一倍，第二点在递归的时候要使用剪枝法，使得多余的一层递归可以省去，虽然答案不唯一，但是要求序列底数总和越大越好，若相等则找序列单个元素较大的一个，我们只需要从sqrt(N)来开始寻找底数即可，之所以底数从sqrt(N)开始是因为P是大于1的最小是2。

AC代码

方法一：
	#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int N,K,P,maxVal=-1;
vector<int> sq,ans,powKey;

void dfs(int idx,int sum,int p,int cnt) {//idx:底数 sum:所有数次方和  p:次方  cnt:底数和
	if(sum==N) {
		if(sq.size()==K&&cnt>maxVal) {//当满足是K个底数组成的和为N且底数和大于之前序列时 
			maxVal=cnt;
			ans=sq;
		}
		return;
	}
	if(idx>=1) {//底数的下界
		sq.push_back(idx);
		if(sum+powKey[idx]<=N&&sq.size()<=K) {//剪枝 当sum+当前数的平方小于K并且当前这个数不是第K个以上的数才进入下一层递归
			dfs(idx,sum+powKey[idx],p,cnt+idx);//选择当前的数
		}
		sq.pop_back();
		dfs(idx-1,sum,p,cnt);//不选择当前的数
	}
}

int main() {
	cin>>N>>K>>P;
	powKey.resize(N+1);//存储1~N每个数的P次方值 
	for(int i=0; i<=N; i++)//提前算好每个数的平方,可以使得时间花费减少一半
		powKey[i]=pow(i,P);
	dfs(sqrt(N),0,P,0);
	if(maxVal==-1) printf("Impossible");
	else {
		cout<<N<<" = ";
		for(int i=0; i<K; i++) {
			printf("%d^%d",ans[i],P);
			if(i<K-1) printf(" + ");
		}
	}
	return 0;
}

方法二：
	#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int N,K,P,maxVal=-1;
vector<int> sq,ans,powKey;

void dfs(int idx,int sum,int p,int cnt) {//idx:底数 sum:所有数次方和  p:次方  cnt:底数和
	if(sum==N) {
		if(sq.size()==K&&cnt>maxVal) {//当满足是K个底数组成的和为N且底数和大于之前序列时 
			maxVal=cnt;
			ans=sq;
		}
		return;
	}
	if(idx>=1) {//底数的下界
		sq.push_back(idx);
		if(sum+powKey[idx]<=N&&sq.size()<=K) {//剪枝 当sum+当前数的平方小于K并且当前这个数不是第K个以上的数才进入下一层递归
			dfs(idx,sum+powKey[idx],p,cnt+idx);//选择当前的数
		}
		sq.pop_back();
		dfs(idx-1,sum,p,cnt);//不选择当前的数
	}
}

int main() {
	cin>>N>>K>>P;
	powKey.resize(N+1);//存储1~N每个数的P次方值 
	for(int i=0; i<=N; i++)//提前算好每个数的平方,可以使得时间花费减少一半
		powKey[i]=pow(i,P);
	dfs(sqrt(N),0,P,0);
	if(maxVal==-1) printf("Impossible");
	else {
		cout<<N<<" = ";
		for(int i=0; i<K; i++) {
			printf("%d^%d",ans[i],P);
			if(i<K-1) printf(" + ");
		}
	}
	return 0;
}

本题拓展：
本题的思路还应用于：
1.在一个背包里固定承重V，不同物品有不同重量和价格，在保证物品重量不超出V情况下，使得物品总价值最大，这种题就是答案唯一的情况。

void DFS(int index, int sumW, int sumC) {
    if (index == n) {
        return;//已经完成对 n 件物品的选择
    }
	
    DFS(index + 1, sumW, sumC);//不选第 index 件物品
    if (sumW + w[index] <= V) {//剪枝 只有加入第 index 件物品后未超过容量 V，才能继续
        if (sumC + c[index] > ans) {
            ans = sumC + c[index];//更新最大价值 maxValue
        }
        DFS(index + 1, sumW + w[index], sumC + c[index]);//选第 index 件物品
    }
}

2.给定 N 个整数（可能有负数），从中选择 K 个数，使得这 K 个数之和恰好等于一个给定的整数 X；如果有多种方案，选择它们中元素平方和最大的一个。数据保证这样的方案唯一。例如，从 4 个整数 {2, 3, 3, 4} 中选择 2 个数，使它们的和为 6，显然有两种方案 {2, 4} 和 {3, 3}，其中平方和最大的方案为 {2, 4}，这种就是答案不唯一的情况。

void DFS(int index, int nowK, int sum, int sumSqu) {
    if (nowK == k && sum == x) {//找到 k 个数的和为 X
        if (sumSqu > maxSumSqu) {//如果比当前找到的更优
            maxSumSqu = sumSqu;//更新最大平方和
            ans = temp;//更新最优方案
        }
        return;
    }
    //已经处理完 n 个数，或者超过 k 个数，或者和超过 x，返回
    if (index == n || nowK > k || sum > x)    return;

    //选 index 号数
    temp.push_back(A[index]);
    DFS(index + 1, nowK + 1, sum + A[index], sumSqu + A[index] * A[index]);
    temp.pop_back();
    //不选 index 号数
    DFS(index + 1, nowK, sum, sumSqu);
}

这类型的题目都可以归纳为一类dfs+剪枝的题型

PAT A1103 Integer Factorization (30 分)

原文：https://www.cnblogs.com/coderJ-one/p/14409000.html