1103 integer factorization (30 points)

The main idea of the topic ： Count a number n, Divide k The number of p The sum of powers .

dfs： Preprocessing a^p <= n All of the a, Then start searching from the maximum number , Pay attention to pruning .

knapsack ： In fact, the capacity is n The backpack can hold the maximum value ( The sum of all numbers is the largest )

Search code

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int N = 10001;
int n,k,p;
int v[N],s = 1,maxsum = -1;
vector<int>res(N),ans;
void dfs(int a,int sum,int cnt,int m)//sum Everyone and ,cnt  frequency 
{  
	if(cnt == k && (m != 0 || sum < maxsum )) return ;
    if(cnt == k && m == 0)
	{
		if(sum > maxsum)
		{
			maxsum = sum;
			ans = res;
		}
		return ;
	}
	for(int i = a; i > 0; i --) // Enumerate each bit from the high order 
	{
	    if(m - v[i] >= 0)
		{
		 res[cnt] = i;// Save the answer 
		 dfs(i,sum + i,cnt + 1,m - v[i]);
		}
	}	
}
int main()
{
	cin >> n >> k >> p;
	while(pow(s,p) <= n)  v[s] = pow(s ,p),s ++;
	s --;
	dfs(s,0,0,n);
	if(maxsum == -1) puts("Impossible");
	else 
	{
		printf("%d = ",n);
		for(int i = 0; i < k; i ++)
		{   
			if(i != 0) printf(" + ");
			printf("%d^%d",ans[i],p);
		}
	}
	return 0;
}

knapsack

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int f[25][410][410];
int n,k,p;
int v[410],w[410],val[410];
int main()
{
	cin >> n >> k >> p;
	int s = 0;//s Item 
	memset(f,-0x3f,sizeof f);
	f[0][0][0] = 0;
	while(pow(s,p) <= n)
	{   
		v[s] = pow(s,p);// Volume 
		//w[s] = 1;// weight   Don't write 
		val[s] = s;// value 
		s ++;
	}
	s --;
	for(int i = 1; i <= s; i ++)
		for(int j = 0; j <= n; j ++)
			for(int z = 0; z <= k; z ++)
			{
				f[i][j][z] = f[i - 1][j][z];
			    if(j - v[i] >= 0 && z >= 1) f[i][j][z] = max(f[i][j][z],f[i][j - v[i]][z - 1] + val[i]);
			}
	if(f[s][n][k] < 0) puts("Impossible");
	else 
	{   
	    int flag = 0;
		printf("%d = ",n);
		for(int i = s,j = n,z = k; i ; i --)
		{
			while(f[i][j][z] == f[i][j - v[i]][z - 1] + val[i])
			{   
				if(flag != 0) printf(" + ");
				printf("%d^%d",i,p);
				j -= v[i],z --;flag = 1;
			}
		}	
	}
	return 0;
}