Java中的动态规划THREE——DP

蒽昨天状态不好休息一天，通宵通的我整个人昏昏的。
前面的两章我们讲解了01背包和完全背包问题，DP的基础模型还剩下部分背包和多重背包，我们将在本章进行讲解多重背包，部分背包问题大家自行学习一下，很简单而且偏向贪心思维。

多重背包问题

与其他问题的对比：

• 01 背包：一个物品只有一件，选或者不选
• 完全背包：一个物品有无数件可以取
• 多重背包：介于上述两种问题之间，题目中限定了该物品的个数

如何实现

基础版：三重循环

在之前的背包问题上，加一层内层循环，从0~n（该物品限定数目），暴力枚举每一个物品目前的数量

例题（FROM 洛谷P1077 ）

代码实现

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerinput=newScanner(System.in);intn=input.nextInt();intm=input.nextInt();int[]a=newint[n];for(inti=0;i<n;i++)a[i]=input.nextInt();long[]dp=newlong[m+1];//dp[j]表示在j盆花的时候有多少方案dp[0]=1;for(inti=0;i<n;i++){for(intj=m;j>=0;j--){longvalue=0;for(intk=0;k<=a[i]&&k<=j;k++)//进行个数的枚举value=(value+dp[j-k])%1000007;dp[j]=value;}}System.out.print(dp[m]);}}

值得注意的是：计数问题（比如本题）不能二进制优化，换句话说，如果题目要求的是方案数则不能使用二进制优化，只能使用三重循环，因为二进制优化不强调路径过程，只强调结果

进阶版：二进制优化时间复杂度

上边的基础版一般来说只能通过一半的数据，一旦数字超过10^3，三重循环的复杂度将来到一个恐怖的数字，于是我们进阶出来了二进制优化的版本。该版本的原理是：将一件物品的限制数目看作一个整体，用二的倍数将其分割为n块，再用01背包问题，遍历该分割后的物品选 or 不选。分割的时候要注意，如果余数已经不足2^n，要将余数直接单独分割成一个物体。比如：一个物品有13个，根据二进制优化，我们将其分为1、2、4、6（余数）。

例题（FROM 洛谷 P1776）

本题将给出两种解法，基础版和进阶版，基础版可以作为三重循环的巩固，但是在题目里只能得到50分，进阶版可以拿满分，但是需要一些理解。

代码实现 - 三重循环

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerinput=newScanner(System.in);intn=input.nextInt();intW=input.nextInt();int[]v=newint[n];int[]w=newint[n];int[]m=newint[n];for(inti=0;i<n;i++){v[i]=input.nextInt();w[i]=input.nextInt();m[i]=input.nextInt();}long[]dp=newlong[W+1];dp[0]=0;//dp[j]表示在j重量的时候最大价值for(inti=0;i<n;i++){for(intj=W;j>=0;j--){for(intk=0;k<=m[i]&&k*w[i]<=j;k++){dp[j]=Math.max(dp[j],dp[j-k*w[i]]+k*v[i]);}}}System.out.print(dp[W]);}}

代码实现 - 二进制优化

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerinput=newScanner(System.in);intn=input.nextInt();intW=input.nextInt();List<Integer>v=newArrayList<>();//动态数组接收分割后的物品价值List<Integer>w=newArrayList<>();//动态数组接收分割后的物品质量for(inti=0;i<n;i++){intvv=input.nextInt();//价值intww=input.nextInt();//质量intmm=input.nextInt();//物品数目限制intk=1;//二进制初始化while(k<=mm){//如果还能分就接着分v.add(vv*k);//将单个价值（vv）与分割大小（k）相乘，得到分割后“本块”的价值w.add(ww*k);//与价值同理，得到质量mm-=k;//每分一块，将总数量减去分割走的数量k*=2;//二进制，1、2、4、8、16…………每次乘2}if(mm>0){//如果不够分了，但是还有余数，把余数单独作为一块v.add(mm*vv);w.add(mm*ww);}}long[]dp=newlong[W+1];//dp[j] 代表在j重量的时候的最大价值for(inti=0;i<w.size();i++){//01背包问题代码intweight=w.get(i);intvalue=v.get(i);for(intj=W;j>=weight;j--){dp[j]=Math.max(dp[j],dp[j-weight]+value);}}System.out.print(dp[W]);}}