PAT甲级1103 Integer Factorization (30 分)：[C++题解]背包问题，DP解法

文章目录

• • 题目分析
  • 题目链接

题目分析

分析
把N（样例中N=169）看成背包的体积；把k(样例中k=5)看成背包能承的重量。把这道题转化为二维完全背包问题。由于数据范围给出的次幂P∈[2,7]，那么p取2的时候，会使得数的个数最多，对应到背包问题，就是物品的数量最多，此时最多是20个物品。因为N最大是400。

对于每个物品，有两个属性：体积和重量
下面的p是次幂，如果是平方，则p=2.

物品序号体积重量价值 = 物品序号

1	$1^p$	1	1
2	$2^p$	1	2
…	…	…	…
$i$	$i^p$	1	$i$
…	…	…	…
20	$20^p$	1	20

问题重述：

给定背包体积为N，背包能装的最大重量为K；

物品序号i从1开始，其价值等于序号；每个物品体积为$i^p$,每个物品的重量都是1.且每个物品可以用无限次。

求恰好把背包装满，价值之和最大的方案。

下面是dp的分析
状态表示：

$f[i][j][k]$表示所有只考虑前i个物品，使得总p次方之和(总的体积)为j，且物品的个数恰好为k 的选法的价值。

状态计算：
对于第i个物品，有很多种选择：可以1个都不选，可以选1次，2次，…,很多次。

状态转移方程（结论）
$f[i][j][k]=max(f[i-1][j][k],f[i][j-i^p][k-1]+i)$

下面是具体的推导过程，不想看的话可以直接用这个状态转移方程。

如果1个都不选，那价值就是$f[i-1][j][k]$;
如果 选1个的话，那价值就是$f[i-1][j-i^p][k-1]+i\times 1$;
如果选 s个话，价值就是$f[i-1][j-i^p\times s][k-s]+i\times s$.

所以，状态转移就是其中的最大值：
$f[i][j][k]=max(f[i-1][j][k],f[i-1][j-i^p][k-1]+i,...,f[i-1][j-i^p\times s][k-s]+i\times s,...)(1式)$

但是状态可以化简令$j=j-i^p,k=k-1$,得到下式：

$f[i][j-i^p][k-1]=max(f[i-1][j-i^p][k-1],f[i-1][j-2i^p][k-2]+i,...,f[i-1][j-i^p\times s][k-s]+i\times s,...)(2式)$

经过对比，1式可以用2式表示，1式max中从第二项开始和2式一一对应，只不过每一项多i，所以将而是带入1式，得：
$f[i][j][k]=max(f[i-1][j][k],f[i][j-i^p][k-1]+i)$

上面就是状态转移的公式。其实和完全背包的状态转移的分析思路一致，如有兴趣，请移步：完全背包dp优化

dp过程的具体代码实现

//三维：需要三重for循环int i;//枚举所有的物品for( i=1; ; i++){int v = power(i ,p);// 物品i的体积：i的p次方if(v > n) break; //背包体积n，已经装不下for(int j = 0; j <= n; j++) //枚举f的第二维 （背包体积）：和为nfor(int k =0; k<= K; k++) //枚举f的第三维（背包承的重量）：数的个数{f[i][j][k] = f[i-1][j][k];//如果f[i][j-v][k-1]合法的话，就转移if( j>= v && k)f[i][j][k] = max(f[i][j][k], f[i][j-v][k-1]+i);}}//退出for循环的条件是第一个不符合的i，所以合法的应该i-1i--;

ac代码

#include<bits/stdc++.h> using namespace std; const int N = 410;int f[21][N][N]; //21个物品，后面是两维背包限制：体积和重量(分别是p次方之和，个数) int n, K, p;//计算a的b次方,用来求i的p次方 int power(int a, int b){int res =1;while(b--) res *= a;return res; } int main(){cin >> n >> K >> p;memset(f ,-0x3f, sizeof f); //初始化为负无穷，表示不存在f[0][0][0] = 0; //初始条件，一个物品都没有，价值为0int i;//枚举所有的物品for( i=1; ; i++){int v = power(i ,p);// 物品i的体积：i的p次方if(v > n) break; //背包体积n，已经装不下for(int j = 0; j <= n; j++) //枚举f的第二维for(int k =0; k<= K; k++) //枚举f的第三维：数的个数{f[i][j][k] = f[i-1][j][k];//如果f[i][j-v][k-1]合法的话，就转移if( j>= v && k)f[i][j][k] = max(f[i][j][k], f[i][j-v][k-1]+i);}}//退出for循环的条件是第一个不符合的i，所以合法的应该i-1i--;if(f[i][n][K] < 0) cout<<"Impossible";//下面是倒序输出具体方案：else{cout<<n<<" = ";bool is_first = true; //用来控制输不输出加号//找方案：倒推,看怎么转移过来的，i选没选？选的话就输出while(i){int v = power(i, p); //体积//正推：如果选i价值大则选i。反过来，如果选i价值大，代表已经选过，应该输出。// >= 左边代表选择i，右边代表不选i//之所有用while，不用if，是因为i可以选择多次while(f[i][n-v][K-1] + i >= f[i-1][n][K]){if(is_first) is_first =false;else cout<<" + ";printf("%d^%d",i,p); //i的p次方 n -= v ,K--; //体积--，数量--}i--; //i处理完了，倒退看看前面的选没选}}}

题目链接

PAT甲级1103 Integer Factorization (30 分)
https://www.acwing.com/problem/content/1595/

总结

以上是生活随笔为你收集整理的PAT甲级1103 Integer Factorization (30 分)：[C++题解]背包问题，DP解法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。