动态规划-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 N=1010; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); for (int i = 1; i <= n; i++) { st=new 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(j>=v[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(j>=v[i])f[i&1][j]=Math.max(f[(i-1)&1][j], f[(i-1)&1][j-v[i]]+w[i]); // else f[i&1][j]=f[(i-1)&1][j]; // } // } // bw.write(f[n&1][m]+""); //一维数组优化 for (int i = 1; i <= n; i++) { for (int j = m; j >= 1; j--) {//注意要从大到小 if(j>=v[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 N=1010; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); for (int i = 1; i <= n; i++) { st=new 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(j>=v[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(j>=v[i])f[i&1][j]=Math.max(f[(i-1)&1][j], f[(i)&1][j-v[i]]+w[i]); // else f[i&1][j]=f[(i-1)&1][j]; // } // } // bw.write(f[n&1][m]+""); //一维数组优化 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) {//注意要从小到大 if(j>=v[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

样例输出

10

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 N=1010; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); for (int i = 1; i <= n; i++) { st=new 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(j>=k*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

样例输出

10

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 N=22010; // 要把 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int p=1; for (int i = 1; i <= n; i++) { st=new StringTokenizer(br.readLine()); int vv=Integer.parseInt(st.nextToken()); int ww=Integer.parseInt(st.nextToken()); int cc=Integer.parseInt(st.nextToken()); int tc=cc; //比如13 可以写成 1+4+8 可以分成3个物品 然后0/1背包去选 int k=1; //比如 13 可以拆出 1 2 4 8不能要（因为要了没那么多物品，13-7=6 ） 6 //可以证明 1 2 4 可以凑出 0-7 的任何数 如果再加上6 就可以凑出 6-13的数 while(cc>k){ v[p]=k*vv; w[p]=k*ww; p++; cc-=k; k<<=1; } if(cc>0){ 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(j>=v[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 N=10010; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int kk = Integer.parseInt(st.nextToken()); for (int i = 1; i <= n; i++) { st=new 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-(v+k)][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​。

1=1；1=1；

2=6−4(2=6−4(天平一边放 66，另一边放 4)；4)；​

3=4−1；3=4−1；

4=4；4=4；

5=6−1；5=6−1；​

6=6；6=6；

7=1+6；7=1+6；

9=4+6−1；9=4+6−1；

10=4+6；10=4+6；

11=1+4+6。11=1+4+6。

评测用例规模与约定

对于 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 N=100010; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); int sum=0; for (int i = 1; i <= n; i++) { w[i]=Integer.parseInt(st.nextToken()); sum+=w[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 res=0; for (int i = 1; i <= sum; i++) { if(f[n][i])res++; } bw.write(res+""); br.close(); bw.flush(); bw.close(); } }