Java|动态规划-整数拆分/完全背包方案数动态规划|算法

题目描述

一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。用f(n)表示n的不同拆分的种数，例如f(7)=6. 要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。输入描述: 每组输入包括一个整数：N(1<=N<=1000000)。输出描述: 对于每组数据，输出f(n)%1000000000。示例1 输入 7 输出 6

解题思路

题目与完全背包问题中，物品体积为2的n次幂 n = 0 , 1 , 2 , . . . n=0,1,2,... n=0,1,2,...，装满背包容量为m的方案总数一致。因此为了形象化地理解这个问题，我们处理该类型的背包问题来解决原问题。
首先，我们设背包容量为 1 ≤ j ≤ 1000000 1≤j≤1000000 1≤j≤1000000，将物品的体积描述为 a [ i ] ( a [ i ] = 2 i , i = 0 , 1 , 2 , . . . , 20 ) a[i](a[i]=2^{i},i=0,1,2,...,20) a[i](a[i]=2i,i=0,1,2,...,20),方案数设为 d p [ j ] ， j dp[j]，j dp[j]，j表示背包容量。显然完全背包问题是可以使用动态规划来计算的。
动态规划的一般步骤（一般动态规划都是求最优化问题，这里求解方案总数所以方法略有不同）
寻找最优子结构的过程变为记录每一个方案的过程：

动态规划的第一步是做一个选择，即最后是放入哪一个物品，所以$dp[j]=dp[j-a[i]]+dp[j],i=0,1,2,...,20$,也就是容量为$j$的背包分别使用物品容量为$1,1、2，1、2、4，...,2^{0}、2^{1}、...、2^{20}$,来进行装包，并且最后装入的物品体积必然不小于之前所装入的物品的体积，并将所有的方案累加，这样的好处是不会产生重复的方案，因为这样做装包的顺序必然是从体积小的到体积大的。例如背包体积为7时，那么放入最后一个物品的选择在放入体积不小于之前放过的物品的体积前提下，方案数为 1. 方案数dp[3](此时，最后一个为体积为4，**添加一个物品不会改变方案数**）； 2.dp[5](此时最后一个物品体积为2）； 3.dp[6](此时，最后一个物品体积为1）；
【Java|动态规划-整数拆分/完全背包方案数】如何保证后一个物品的体积大于等于前面的物品体积？
我们可以采用for循环的方式，向使用体积小的物品。伪代码如下：

for i =1 to 20//物品从小到大选择 for j = a[i] to n//背包容量从小到大，且必然空包至少能够放下当前选择的物品，这里表示背包容量从a[i]到n的背包不断尝试放最后一个体积为a[i]的物品（注意此时a[i]必然大于已经放入背包的物品的体积） dp[j]+=dp[j-a[i]]//这里表示将最后一个物品体积从1、2、4、8、....、2^20的所有方案相加。

子问题重叠
从 d p [ j ] = d p [ j ? a [ i ] ] + d p [ j ] , i = 0 , 1 , 2 , . . . , 20 dp[j]=dp[j-a[i]]+dp[j],i=0,1,2,...,20 dp[j]=dp[j?a[i]]+dp[j],i=0,1,2,...,20,可以看出，当我们从小到大计算dp[j]时，则在计算 d p [ j ] dp[j] dp[j]时，必然已知 d p [ j ? a [ i ] ] dp[j-a[i]] dp[j?a[i]],这样可以减少计算。
以下给出该问题的状态转移方程：注意：dp[0]=1，因为假如一开始什么也不放，然后放入体积为a[i]的物品也算一种方案
d p [ j ] = { 1.............................. j = 0 ∑ 0 20 d p [ j ? a [ i ] ] . . . . j ? a [ i ] > 0 dp[j]=\left\{\begin{matrix} 1..............................j=0\\ \sum_{0}^{20}dp[j-a[i]]....j-a[i]> 0 \end{matrix}\right. dp[j]={1..............................j=0∑020?dp[j?a[i]]....j?a[i]>0?
以下为伪代码：

let a[1...20] and dp[0...n]be new arrays//a用于记录物品体积，dp[j]用于记录背包容量为j时方案数,n为给出的背包容量 for i =1 to 20//初始化物品体积 a[i] = 2^(i-1) dp[0]=1//原因见子问题重叠处加粗字体 for i = 1 to 20 //寻找所有方案 for j=a[i] to n//背包容量从a[i]到n dp[j] +=dp[j-a[i]]//将所有方案数相加 return dp

以下为java代码实现

import java.util.Scanner; public class INTEGER_SPLIT { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int i, j, t; int n; int[] dp = new int[1000002]; int[] a = new int[21]; for (i = 1; i <= 20; i++) a[i] = (1 << (i - 1)); dp[0] = 1; n = scanner.nextInt(); for (i = 1; i <= 20; i++) { for (j = a[i]; j <= n; j++) { dp[j] += dp[j - a[i]]; dp[j] %= 1000000000; } } System.out.println(dp[n]); } } }

测试结果：