题意 : 给出一个数 n ，问如果使用 2 的幂的和来组成这个数 n 有多少种不同的方案？
分析 :
完全背包解法
将问题抽象==>有重量分别为 2^0、2^1、2^2…2^k 的物品且每种物品可无限取，问有多少种方案来填满容量为 n 的背包？
之前并不知道背包还能用来计数.......
有一道裸的背包计数问题可以作为练习 ==> HDU 1284
定义 dp[ i ][ j ] 为前 i 种物品组成总重量 j 的方案数为多少、初始化为 dp[ 0 ][ 0 ] = 1 其他为 0
则状态转移方程为 dp[ i ][ j ] += dp[ i-1 ][ j - k*w[ i ] ] ( k ≥ 0 && j ≥ k*w[i] )
最后类似于完全背包的递推方程，可化简为一维线性的递推式 dp[ j ] += dp[ j - w[ i ] ] ( j ≥ w[i] )
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; const int mod = 1e9; int dp[maxn]; int main(void) { int n; while(~scanf("%d", &n)){ memset(dp, 0, sizeof(dp)); dp[0] = 1; for(int i=0; i<20; i++) for(int j=(1<<i); j<=n; j++){ dp[j] += dp[j-(1<<i)]; if(dp[j] >= mod) dp[j] -= mod; } printf("%d ", dp[n]); } return 0; }
找递推规律解法
现分别来考虑 n 为奇数还有偶数的情况
① n 为奇数的时候可以发现只是在 n-1( 偶数 ) 每种方案的后面多了个 1 而已并不能多组出新的方案，所以 dp[ 奇数 ] = dp[ 奇数 -1 ]
② n 为偶数，此时可以将所有的方案数分成两类 ( 组合方案中包含 1 的 ) 与 ( 组合方案中不包含 1 的 )
首先来看组合方案中包含 1 的情况
可以将其看成在 n-1 的方案中每个方案的后面多加一个 1 来组成，此时方案数和 n-1 是一样的即 dp[ n - 1 ]
而组合方案中不包含 1 的情况
如果将小数据打表列出来会发现这种情况的方案数实际等于 n/2 的方案数，即 dp[ n/2 ]
所以最后的答案应该为 dp[ n ] = dp[ n-1 ] + dp[ n/2 ]
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; const int mod = 1e9; int dp[maxn]; int main(void) { int n; while(~scanf("%d", &n)){ dp[1] = 1; dp[2] = dp[3] = 2; dp[4] = dp[5] = 4; dp[6] = dp[7] = 6; if(n <= 7) printf("%d ", dp[n]); else{ for(int i=8; i<=n; i++){ if(i&1) dp[i] = dp[i-1]; else dp[i] = dp[i-2] + dp[i>>1]; if(dp[i] >= mod) dp[i] -= mod; } printf("%d ", dp[n]); } } return 0; }
现举几个例子来解释一下
dp[1] = 1
1
------------------------------------------------------------------------------------
dp[2] = 2
1+1、2
------------------------------------------------------------------------------------
dp[3] = dp[3-1] = 2
1+1+1、2+1 ( 奇数情况 == 奇数-1中所有方案数后面添 1 )
------------------------------------------------------------------------------------
dp[4] = dp[4-1] + dp[4/2] = 4
1+1+1+1、2+1+1 ( 这个就是 dp[4-1] 的情况 == 在 n-1 的所有方案数后面添 1 )
2+2、4 ( 这里的所有方案 / 2 后会发现实际就对应了 dp[2] ，所以是 dp[ 4/2 ] )
------------------------------------------------------------------------------------
dp[5] = dp[5-1] = 4
1+1+1+1+1、2+1+1+1
2+2+1、4+1
------------------------------------------------------------------------------------
dp[6] = dp[6-1] + dp[ 6/2 ] = 6
1+1+1+1+1+1、2+1+1+1+1、2+2+1+1、4+1+1 ( 此为 dp[ 6-1 ] 意义和上面所述一样 )
2+2+2、4+2 ( 方案所有数 / 2 后变成 1+1+1、2+1 和 dp[3] 是对应的! )
......