本文主要是介绍poj 3132 Sum of Different Primes（01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
给你两个数n和m，求有多少种方式，使得m个不同的素数和为n。当n = 24 m = 3 的时候，只有二种 {2, 3, 19} and {2, 5, 17}。
解题思路：
因为题目给的n和m都比较小，所以可以暴力求解。
因为每个在集合里每个素数只能出现一次，这个特性符合01背包问题。设：dp[i][j] 表示 和为 i 并且 有 j 个素数组成的方法数。
很明显，dp[i][j] += dp[i - p[k]][j - 1];
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int p[1111],pNum;
//线性素数筛
void pre(int num)
{int a[2222];pNum = 0;memset(a,0,sizeof(a));int i,j;for(i=2; i<=num; i++){if(!a[i])p[pNum++]=i;//没有else iffor(j=0; j<pNum&&i*p[j]<=num; j++){a[i*p[j]]=1;if(!(i%p[j]))break;//这边是能够整除的时候跳出，一开始写成了if(i%p[j])}}
}
int dp[2222][222];
int main()
{pre(1122);int n,m,i,j,t;while(scanf("%d%d",&n,&m)==2){if(n==0&&m==0)break;memset(dp,0,sizeof(dp));dp[0][0]=1;for(i=0; i<pNum&&p[i]<=n; i++){for(t=m; t>=1; t--)//由t个素数组成{for(j=n; j>=p[i]; j--)//容量从大到小，01背包的做法{dp[j][t]+=dp[j-p[i]][t-1];}}}printf("%d\n",dp[n][m]);}return 0;
}
这篇关于poj 3132 Sum of Different Primes（01背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
