动态规划-01背包（模板）、完全背包（模板）、多重背包1（模板）、多重背包2（模板）、背包与魔法、砝码称重-北京尧图网络

问题描述有 NN 件物品和一个体积为 MM 的背包。第 ii 个物品的体积为 vivi价值为 wiwi。每件物品只能使用一次。请问可以通过什么样的方式选择物品使得物品总体积不超过 MM 的情况下总价值最大输出这个最大价值即可。输入格式第一行输入两个正整数 N,MN,M。(1≤N,M≤1000)(1≤N,M≤1000)接下来 NN 行每行输入两个整数 vi,wivi,wi。(0≤vi,wi≤1000)(0≤vi,wi≤1000)输出格式输出一个整数表示符合题目要求的最大价值。样例输入4 5 1 2 2 4 3 4 4 5样例输出8说明你可以选择第二个物品和第三个物品。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N1010; static int v[]new int[N]; static int w[]new int[N]; static int f[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); v[i]Integer.parseInt(st.nextToken()); w[i]Integer.parseInt(st.nextToken()); } //定义f[i][j]为只考虑前i件背包体积不超过j的最大价值 // for (int i 1; i n; i) { // for (int j 1; j m; j) { // if(jv[i])f[i][j]Math.max(f[i-1][j], f[i-1][j-v[i]]w[i]); // else f[i][j]f[i-1][j]; // } // } // 空间上可以用两行优化可以利用行的奇偶性来进行区分 // for (int i 1; i n; i) { // for (int j 1; j m; j) { // if(jv[i])f[i1][j]Math.max(f[(i-1)1][j], f[(i-1)1][j-v[i]]w[i]); // else f[i1][j]f[(i-1)1][j]; // } // } // bw.write(f[n1][m]); //一维数组优化 for (int i 1; i n; i) { for (int j m; j 1; j--) {//注意要从大到小 if(jv[i])f[j]Math.max(f[j], f[j-v[i]]w[i]); } } bw.write(f[m]); br.close(); bw.flush(); bw.close(); } }完全背包模板问题描述有 NN 件物品和一个体积为 MM 的背包。第 ii 个物品的体积为 vivi价值为 wiwi。每件物品可以使用无限次。请问可以通过什么样的方式选择物品使得物品总体积不超过 MM 的情况下总价值最大输出这个最大价值即可。输入格式第一行输入两个正整数 N,MN,M。(1≤N,M≤1000)(1≤N,M≤1000)接下来 NN 行每行输入两个整数 vi,wivi,wi。(0≤vi,wi≤1000)(0≤vi,wi≤1000)输出格式输出一个整数表示符合题目要求的最大价值。样例输入4 5 1 2 2 4 3 4 4 5样例输出10说明你可以选择 11 个第一个物品和 22 个第二个物品。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N1010; static int v[]new int[N]; static int w[]new int[N]; static int f[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); v[i]Integer.parseInt(st.nextToken()); w[i]Integer.parseInt(st.nextToken()); } //定义f[i][j]为只考虑前i件背包体积不超过j的最大价值 // f[i , j ] max( f[i-1,j] , f[i-1,j-v]w , f[i-1,j-2*v]2*w , f[i-1,j-3*v]3*w , .....) // f[i , j-v] max( f[i-1,j-v] , f[i-1,j-2*v] w , f[i-1,j-3*v]2*w , .....) // 由上两式可得出如下递推关系 // f[i][j]max(f[i,j-v]w , f[i-1][j]) // for (int i 1; i n; i) { // for (int j 1; j m; j) { // if(jv[i])f[i][j]Math.max(f[i-1][j], f[i][j-v[i]]w[i]); // else f[i][j]f[i-1][j]; // } // } // 空间上用两行优化可以利用行的奇偶性来进行区分 // for (int i 1; i n; i) { // for (int j 1; j m; j) { // if(jv[i])f[i1][j]Math.max(f[(i-1)1][j], f[(i)1][j-v[i]]w[i]); // else f[i1][j]f[(i-1)1][j]; // } // } // bw.write(f[n1][m]); //一维数组优化 for (int i 1; i n; i) { for (int j 1; j m; j) {//注意要从小到大 if(jv[i])f[j]Math.max(f[j], f[j-v[i]]w[i]); } } bw.write(f[m]); br.close(); bw.flush(); bw.close(); } }多重背包1模板问题描述有 NN 件物品和一个体积为 MM 的背包。第 ii 个物品的体积为 vivi价值为 wiwi。每件物品只能使用 cici 次。请问可以通过什么样的方式选择物品使得物品总体积不超过 MM 的情况下总价值最大输出这个最大价值即可。输入格式第一行输入两个正整数 N,MN,M。(1≤N,M≤100)(1≤N,M≤100)接下来 NN 行每行输入三个整数 vi,wi,civi,wi,ci。(0≤vi,wi,ci≤100)(0≤vi,wi,ci≤100)输出格式输出一个整数表示符合题目要求的最大价值。样例输入4 5 1 2 3 2 4 1 3 4 3 4 5 2样例输出10import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N1010; static int v[]new int[N]; static int w[]new int[N]; static int c[]new int[N]; static int f[][]new int[N][N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); v[i]Integer.parseInt(st.nextToken()); w[i]Integer.parseInt(st.nextToken()); c[i]Integer.parseInt(st.nextToken()); } //定义f(i,j)为只考虑前i件物品背包体积不超过j 的最大价值 for (int i 1; i n ;i) { for (int j 1; j m; j) { f[i][j]f[i-1][j]; for (int k 1; k c[i]; k) { if(jk*v[i])f[i][j]Math.max(f[i][j],f[i-1][j-k*v[i]]k*w[i]); } } } bw.write(f[n][m]); br.close(); bw.flush(); bw.close(); } }多重背包2模板问题描述有 NN件物品和一个体积为 MM的背包。第 ii个物品的体积为 vivi价值为 wiwi。每件物品只能使用 cici 次。请问可以通过什么样的方式选择物品使得物品总体积不超过 MM的情况下总价值最大输出这个最大价值即可。由于评测机过快本题数据于 2024-12-16 加强N,MN,M上调至 2×1032×103以杜绝多重背包1的做法通过输入格式第一行输入两个正整数 N,MN,M。(1≤N,M≤2000)(1≤N,M≤2000)接下来 NN行每行输入三个整数 vi,wi,civi,wi,ci。(1≤vi,wi,ci≤2000)(1≤vi,wi,ci≤2000)输出格式输出一个整数表示符合题目要求的最大价值。样例输入4 5 1 2 3 2 4 1 3 4 3 4 5 2样例输出10import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N22010; // 要把 2000 完全拆开比如拆成 1, 2, 4, ..., 1024, 剩余最多需要 11 个分组。 // 所以总的分组数上限 2000 × 11 22000。 static int v[]new int[N]; static int w[]new int[N]; static int c[]new int[N]; static int f[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); int p1; for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); int vvInteger.parseInt(st.nextToken()); int wwInteger.parseInt(st.nextToken()); int ccInteger.parseInt(st.nextToken()); int tccc; //比如13 可以写成 148 可以分成3个物品然后0/1背包去选 int k1; //比如 13 可以拆出 1 2 4 8不能要因为要了没那么多物品13-76 6 //可以证明 1 2 4 可以凑出 0-7 的任何数如果再加上6 就可以凑出 6-13的数 while(cck){ v[p]k*vv; w[p]k*ww; p; cc-k; k1; } if(cc0){ v[p]cc*vv; w[p]cc*ww; p; } } //定义f(i,j)为只考虑前i件物品背包体积不超过j 的最大价值 for (int i 1; i p ;i) { for (int j m; j 1; j--) { if(jv[i])f[j]Math.max(f[j],f[j-v[i]]w[i]); } } bw.write(f[m]); br.close(); bw.flush(); bw.close(); } }背包与魔法题目描述小蓝面前有 N 件物品其中第 i 件重量是 Wi价值是 Vi。她还有一个背包最大承重是 M。小蓝想知道在背包称重范围内她最多能装总价值多少的物品特别值得一提的是小蓝可以使用一个魔法将一件物品的重量增加 K同时价值翻倍。(当然小蓝也可以不使用魔法输入格式第一行包含 3 个整数 N、M 和 K。以下 N 行每行两个整数 Wi 和 Vi。输出格式一个整数代表答案。样例输入3 10 3 5 10 4 9 3 8样例输出26提示选择第二件和第三件物品同时对第二件物品使用魔法。对于 30% 的数据1 ≤ N, M, K ≤ 100.对于 100% 的数据1 ≤ N ≤ 2000, 1 ≤ M, K ≤ 10000, 0 ≤ Wi , Vi ≤ 10000.import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N10010; static int v[]new int[N]; static int w[]new int[N]; static int c[]new int[N]; static int f[][]new int[N][2]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); int kk Integer.parseInt(st.nextToken()); for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); v[i]Integer.parseInt(st.nextToken()); w[i]Integer.parseInt(st.nextToken()); } //本题相对于零一背包问题多了一个状态也就是当前位置使用魔法的次数 //可以分为两种情况当前位置是否使用魔法注意只是当前位置不代表之前所有 //定义f(i,j,k)为考虑前i件物品背包体积不超过j 一直到当前位置使用k次魔法的最大价值 //f[i][j][0]max(f[i-1][j][0],f[i-1][j-v][0]w); //计算f[i][j][1]这个要分是否在本位置使用魔法 //若不使用 f[i][j][1]max( f[i-1][j][1],f[i-1][j-v][1]w); //若使用 f[i][j][1]max(f[i][j][1],f[i-1][j-(vk)][1]2*w); for (int i 1; i n ;i) { for (int j m; j 0; j--) { //这里要注意题目的重量可以等于0 if(j-v[i]0)f[j][0]Math.max(f[j][0],f[j-v[i]][0]w[i]); if(j-v[i]0)f[j][1]Math.max( f[j][1],f[j-v[i]][1]w[i]); if(j-(v[i]kk)0)f[j][1]Math.max(f[j][1],f[j-(v[i]kk)][0]2*w[i]); } } bw.write(Math.max(f[m][0], f[m][1])); br.close(); bw.flush(); bw.close(); } }砝码称重问题描述你有一架天平和 NN 个砝码这 NN 个砝码重量依次是 W1,W2,⋅⋅⋅,WNW1,W2,⋅⋅⋅,WN。请你计算一共可以称出多少种不同的重量注意砝码可以放在天平两边。输入格式输入的第一行包含一个整数 NN。第二行包含 NN 个整数W1,W2,W3,⋅⋅⋅,WNW1,W2,W3,⋅⋅⋅,WN。输出格式输出一个整数代表答案。样例输入3 1 4 6样例输出10样例说明能称出的 1010 种重量是1、2、3、4、5、6、7、9、10、111、2、3、4、5、6、7、9、10、11。111126−4(26−4(天平一边放 66另一边放 4)4)34−134−1444456−156−16666716716946−1946−11046104611146。11146。评测用例规模与约定对于 5050的评测用例1≤N≤151≤N≤15。对于所有评测用例1≤N≤100,N1≤N≤100,N个砝码总重不超过 100000100000。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N100010; static int w[]new int[N]; static boolean f[][]new boolean[110][N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); int sum0; for (int i 1; i n; i) { w[i]Integer.parseInt(st.nextToken()); sumw[i]; } //定义f[i][j]为只考虑前i件砝码是否能称出重量j的重物 for (int i 0; i n; i) { f[i][0]true; } for (int i 1; i n; i) { for (int j 1; j sum; j) { //如果前 i-1 个砝码已经能称出重量 j那么不加第 i 个砝码自然也能称出 j f[i][j]|f[i-1][j]; //将第 i 个砝码放在重物j一侧 // 设想天平左边放重物未知重量右边放砝码。如果重物重量为 j第 i 个砝码放在重物同侧即和重物一起在左边 // 那么右边只需要平衡重量 j w[i] 即可因为左边总重 j w[i]右边为 j w[i] 时平衡。 if(j w[i]sum)f[i][j]|f[i-1][j w[i]]; //将第 i 个砝码与重物j不放在一侧 //设重物在左边重量为 j 第 i 个砝码放在右边 //如果砝码比重物轻若想称出重物j 取决于能不能称出 j - w[i] if(j w[i])f[i][j]|f[i-1][j - w[i]]; //如果砝码比重物重若想称出重物j 取决于能不能称出 w[i] - j else if(w[i] j)f[i][j]|f[i-1][w[i]-j]; } } int res0; for (int i 1; i sum; i) { if(f[n][i])res; } bw.write(res); br.close(); bw.flush(); bw.close(); } }

动态规划-01背包（模板）、完全背包（模板）、多重背包1（模板）、多重背包2（模板）、背包与魔法、砝码称重

相关推荐

超级电容壳体激光封焊：AIDC供电安全的最后一道防线

焊接产线数字孪生：从“盲焊“到数据驱动

Torzu：重新定义Switch模拟体验的开源革新者

更多资讯

宜春铜鼓考电工证怎么考内部消息告诉你怎么破学历门槛

办理考低压电工证的试卷需要什么材料

潍坊考低压电工证在哪考?实操考试心里没底怕挂科

低压电工证分几科通过率揭秘：刚需证书怎么考最稳妥

工地太忙根本没时间复习考试？敦煌电工证培训学校通过率揭秘来了

别踩坑！学历不高也能考电工焊工证，抖音推广电工证焊工证选对机构太关键

今日更新

西昌市电工作业查询怎么查？郑州报考避坑指南帮你少走弯路

西昌市电工作业查询通过率揭秘：怕考不过白交培训费？这几点要记牢

临夏电工证在哪里审官方报名入口怎么找

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？