文章目錄

• • 題目分析
  • 題目鏈接

題目分析

分析
把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解法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。