动态规划-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−1​6666716716946−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(); } }