Java中的DP-260316多重背包问题如何实现基础版三重循环例题FROM 洛谷P1077 代码实现进阶版二进制优化时间复杂度例题FROM 洛谷 P1776代码实现 - 三重循环代码实现 - 二进制优化蒽昨天状态不好休息一天通宵通的我整个人昏昏的。前面的两章我们讲解了01背包和完全背包问题DP的基础模型还剩下部分背包和多重背包我们将在本章进行讲解多重背包部分背包问题大家自行学习一下很简单而且偏向贪心思维。多重背包问题与其他问题的对比01 背包一个物品只有一件选或者不选完全背包一个物品有无数件可以取多重背包介于上述两种问题之间题目中限定了该物品的个数如何实现基础版三重循环在之前的背包问题上加一层内层循环从0~n该物品限定数目暴力枚举每一个物品目前的数量例题FROM 洛谷P1077 代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinputnewScanner(System.in);intninput.nextInt();intminput.nextInt();int[]anewint[n];for(inti0;in;i)a[i]input.nextInt();long[]dpnewlong[m1];//dp[j]表示在j盆花的时候有多少方案dp[0]1;for(inti0;in;i){for(intjm;j0;j--){longvalue0;for(intk0;ka[i]kj;k)//进行个数的枚举value(valuedp[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){ScannerinputnewScanner(System.in);intninput.nextInt();intWinput.nextInt();int[]vnewint[n];int[]wnewint[n];int[]mnewint[n];for(inti0;in;i){v[i]input.nextInt();w[i]input.nextInt();m[i]input.nextInt();}long[]dpnewlong[W1];dp[0]0;//dp[j]表示在j重量的时候最大价值for(inti0;in;i){for(intjW;j0;j--){for(intk0;km[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){ScannerinputnewScanner(System.in);intninput.nextInt();intWinput.nextInt();ListIntegervnewArrayList();//动态数组接收分割后的物品价值ListIntegerwnewArrayList();//动态数组接收分割后的物品质量for(inti0;in;i){intvvinput.nextInt();//价值intwwinput.nextInt();//质量intmminput.nextInt();//物品数目限制intk1;//二进制初始化while(kmm){//如果还能分就接着分v.add(vv*k);//将单个价值vv与分割大小k相乘得到分割后“本块”的价值w.add(ww*k);//与价值同理得到质量mm-k;//每分一块将总数量减去分割走的数量k*2;//二进制1、2、4、8、16…………每次乘2}if(mm0){//如果不够分了但是还有余数把余数单独作为一块v.add(mm*vv);w.add(mm*ww);}}long[]dpnewlong[W1];//dp[j] 代表在j重量的时候的最大价值for(inti0;iw.size();i){//01背包问题代码intweightw.get(i);intvaluev.get(i);for(intjW;jweight;j--){dp[j]Math.max(dp[j],dp[j-weight]value);}}System.out.print(dp[W]);}}
Java中的动态规划THREE——DP
发布时间：2026/7/30 1:59:16
Java中的DP-260316多重背包问题如何实现基础版三重循环例题FROM 洛谷P1077 代码实现进阶版二进制优化时间复杂度例题FROM 洛谷 P1776代码实现 - 三重循环代码实现 - 二进制优化蒽昨天状态不好休息一天通宵通的我整个人昏昏的。前面的两章我们讲解了01背包和完全背包问题DP的基础模型还剩下部分背包和多重背包我们将在本章进行讲解多重背包部分背包问题大家自行学习一下很简单而且偏向贪心思维。多重背包问题与其他问题的对比01 背包一个物品只有一件选或者不选完全背包一个物品有无数件可以取多重背包介于上述两种问题之间题目中限定了该物品的个数如何实现基础版三重循环在之前的背包问题上加一层内层循环从0~n该物品限定数目暴力枚举每一个物品目前的数量例题FROM 洛谷P1077 代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinputnewScanner(System.in);intninput.nextInt();intminput.nextInt();int[]anewint[n];for(inti0;in;i)a[i]input.nextInt();long[]dpnewlong[m1];//dp[j]表示在j盆花的时候有多少方案dp[0]1;for(inti0;in;i){for(intjm;j0;j--){longvalue0;for(intk0;ka[i]kj;k)//进行个数的枚举value(valuedp[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){ScannerinputnewScanner(System.in);intninput.nextInt();intWinput.nextInt();int[]vnewint[n];int[]wnewint[n];int[]mnewint[n];for(inti0;in;i){v[i]input.nextInt();w[i]input.nextInt();m[i]input.nextInt();}long[]dpnewlong[W1];dp[0]0;//dp[j]表示在j重量的时候最大价值for(inti0;in;i){for(intjW;j0;j--){for(intk0;km[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){ScannerinputnewScanner(System.in);intninput.nextInt();intWinput.nextInt();ListIntegervnewArrayList();//动态数组接收分割后的物品价值ListIntegerwnewArrayList();//动态数组接收分割后的物品质量for(inti0;in;i){intvvinput.nextInt();//价值intwwinput.nextInt();//质量intmminput.nextInt();//物品数目限制intk1;//二进制初始化while(kmm){//如果还能分就接着分v.add(vv*k);//将单个价值vv与分割大小k相乘得到分割后“本块”的价值w.add(ww*k);//与价值同理得到质量mm-k;//每分一块将总数量减去分割走的数量k*2;//二进制1、2、4、8、16…………每次乘2}if(mm0){//如果不够分了但是还有余数把余数单独作为一块v.add(mm*vv);w.add(mm*ww);}}long[]dpnewlong[W1];//dp[j] 代表在j重量的时候的最大价值for(inti0;iw.size();i){//01背包问题代码intweightw.get(i);intvaluev.get(i);for(intjW;jweight;j--){dp[j]Math.max(dp[j],dp[j-weight]value);}}System.out.print(dp[W]);}}
