完全背包（模板）
前言：完全背包问题，只是在0,1背包问题上稍微改变了一点，就是这里的物品可以重复选择。
例题1：完全背包__牛客网
1. 题目解析（这个题目说的很清楚了）
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
2. 算法原理
1.状态表示
根据0,1背包问题，
我们对于 问题一 设：f[ i ][ j ]表示在前 i 个物品中选出的物品 总体积不大于j的总质量最大值；
问题二 设：g[ i ] [ j ] 表示在前 i 个物品中选出的物品 总体积等于j的总质量最大值；
只是我们这里需要，对 i 位置的物品 进行枚举，i 位置的物品可能是 1个，2个，3个,......
(满足j >= n * v[ i ] 就行 )
2.状态表示转移方程
对于i位置的物品 ： 选 dp[ i ][ j ] = 满足 （j >= n * v [ i ]） 即可
Math.max( dp[ i - 1 ][ j ] ，dp[ i - 1 ] [ j - v[ i ]] + w[ i ]，dp[ i - 1][ j - 2 * v[ j ]] + 2 * w[ i ] + ....)
不选： dp[ i ][ j ] = dp[i - 1][ j ]
3.初始化
int[ ][ ] f = new int[n + 1][v + 1]; int[ ][ ] g = new int[n + 1][v + 1];
对于这多加的一行，一列，初始化的值应为0。（原因如下：）
对于 0 个物品，背包体积无论多大，能选出物品价值都为0；
对于无数个物品，背包体积为 0 ，能选出物品价值都为0；
4.填表顺序
对于dp[ i ][ j ] 依赖与 dp[ i - 1][ j ] , dp[ i - 1][ j - xx] 也就是左上方的值；所以我们
从 左 -> 右，上 -> 下 填表。
5.返回值
由状态表示可得： 问题1为 f[ n ][ v ] ； 问题2为 f[ n ][ v ]。
3. 代码
public class Solution {public ArrayList<Integer> knapsack (int v, int n,ArrayList<ArrayList<Integer>> nums) {int[][] f = new int[n + 1][v + 1];int[][] g = new int[n + 1][v + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= v; j++) {int tep = nums.get(i - 1).get(0);for (int k = 0; k * tep <= j; k++) {f[i][j] = Math.max(f[i][j], f[i - 1][j]);g[i][j] = Math.max(g[i][j], g[i - 1][j]);if (tep <= j) {f[i][j] = Math.max(f[i][j], f[i - 1][j - tep * k] + nums.get(i - 1).get(1) * k);}if(g[i-1][j - k*tep] != 0 || k * tep == j){g[i][j] = Math.max(g[i][j],g[i-1][j- k*tep] + nums.get(i - 1).get(1) * k);}}}}ArrayList<Integer> ret = new ArrayList<>();ret.add(f[n][v]);ret.add(g[n][v]);return ret;}
}4. 优化：（实现 O(n3) -> O(n2) ）(这一步说实话真的太强了)
等式一：
f[i][j] = max(f[i-1][j], f[i-1][j - v[i]]+w[i], f[i-1][j-2*v[i]]+2*w[i], f[i-1][j-3*v[i]]+3*w[i] ,......)使用代入法，将j= j - v[i]带入上面的方程中得到：
等式二：
f[i][j-v[i]] = max(f[i-1][j-v[i]], f[i-1][j - 2*v[i]]+w[i], f[i-1][j-3*v[i]]+2*w[i], f[i-1][j-3*v[i]]+3*w[i] ,......)对比等式一，等式二，可化简为: (如此便可代替循环选多少个当前物品最佳)
f[i][j] = max(f[i-1][j], f[i][j - v[i]]+w[i]);
import java.util.*;public class Solution {public ArrayList<Integer> knapsack (int v, int n, ArrayList<ArrayList<Integer>> nums) {int[][] f = new int[n + 1][v + 1];int[][] g = new int[n + 1][v + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= v; j++) {int tep = nums.get(i - 1).get(0);f[i][j] = f[i - 1][j];g[i][j] = g[i - 1][j];if (tep <= j) {f[i][j] = Math.max(f[i][j], f[i][j - tep] + nums.get(i - 1).get(1));} if(tep == j || (tep < j && g[i][j - tep] != 0) ){g[i][j] = Math.max(g[i][j],g[i][j- tep] + nums.get(i - 1).get(1));}}}ArrayList<Integer> ret = new ArrayList<>();ret.add(f[n][v]);ret.add(g[n][v]);return ret;}
}例题2：最少的完全平方数_牛客题霸_牛客网 （变式）
1. 题目解析
通过举例表明题目意思
给出 n = 9 , 可提供选择的数有 1 ，4，9，16，25，36...，81，每个数可重复选；
选出m 个数要求和为n，求最小值m，这里选9，m = 1;
2. 算法原理
1.状态表示
设：dp[ i ] [ j ]表示在前i个数中选出 x 个可重复的数 和等于n,x的最小值。
2.状态表示转移方程
由完全背包化简的表达过程得：
选 i 位置 dp[ i ] [ j ] = Math.min( dp [ i - 1][ j ], dp [ i ] [ j - i * i ] + 1)，需满足条件
(i * i == j || (i * i < j && dp[i][j - i*i] != 0)) ；
不选：dp[ i ][ j ] = dp[ i - 1][ j ];
3.初始化
int[][] dp = new int[m+1][n+1];
对于dp[ 0 ][ xx ] 0 个可选的数，但要求选出数的和 和为 n ，这是不可能的，所以我们初始化为 0x3f3f3f3f,这样就选不到，这一行的值了。
对于 dp[ xx ][ 0 ] xx 给可选的数，但要求选出数的和为0，不选就可以了，所以初始化为0。
4.填表顺序
根据当前位置依赖之前位置的关系，这里是 左 -> 右，上 ->下。
5.返回值
根据状态表示的返回值为： dp [m] [n]
3. 代码
import java.util.Scanner;public class Main {public static void main(String[] args) {// 处理初始化，输出Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = (int)Math.sqrt(n);int[][] dp = new int[m+1][n+1];for(int j = 0;j <= n;j++){dp[0][j] = 0x3f3f3f3f;}dp[0][0] = 0;// 核心代码for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){dp[i][j] = dp[i-1][j];if(i * i == j || (i * i < j && dp[i][j - i*i] != 0)){dp[i][j] = Math.min(dp[i][j],dp[i][j - i*i] + 1);}}}System.out.println(dp[m][n]);}
}上面如有表述不好的，欢迎评论区留言。