flash网站建设教程,下载爱南宁官方网站,wordpress 分类模板指定,网站后台放在哪里背包问题之前的C语言版本已经将思路解析的差不多#xff0c;虽然还有些许错误需要改正#xff0c;但大体思路是正确的#xff0c;需要的读者请参阅动态规划之背包问题#xff08;C语言#xff09; 背包问题本身就是典型的动态规划问题#xff0c;所以这里只给出动态规划…背包问题之前的C语言版本已经将思路解析的差不多虽然还有些许错误需要改正但大体思路是正确的需要的读者请参阅动态规划之背包问题C语言 背包问题本身就是典型的动态规划问题所以这里只给出动态规划的算法。
0-1背包
思路一常规做法
import java.util.Scanner;public class Main {static Scanner in new Scanner(System.in);static int[] v,w;static int[][] d;static int n, c;public static void main(String[] args) {n in.nextInt();c in.nextInt();v new int[n1];w new int[n1];d new int[c1][c1];for (int i 1; i n; i) {v[i] in.nextInt();w[i] in.nextInt();}/*** d(i, j) max{d(i1, j), d(i1, j - V[i]) W[i]}* d(i, j)表示把第i, i1, i2...n个物品装到容量为 j 的背包中的最大总重量* 所以i必须逆序 j无所谓* */for(int i n; i 1; i--) {for(int j 0; j c; j) {d[i][j] (in ? 0 : d[i1][j]);if(j v[i]) {d[i][j] Math.max(d[i][j],d[i1][j-v[i]]w[i]);}}}System.out.println(d[1][c]);}
}
思路二滚动数组在输入数据的时候就进行处理
import java.util.Scanner;public class Main {static Scanner in new Scanner(System.in);static int[] v,w;static int[][] d;static int n, c;public static void main(String[] args) {n in.nextInt();c in.nextInt();v new int[n1];w new int[n1];d new int[c1][c1];/*** d(i, j) max{d(i-1, j), d(i-1, j - V[i]) W[i]}* d(i, j)表示把第前 i 个物品物品装到容量为 j 的背包中的最大总重量* */for(int i 1; i n; i) {int v in.nextInt();int w in.nextInt();for(int j 0; j c; j) {d[i][j] (i1 ? 0 : d[i-1][j]);if(j v) {d[i][j] Math.max(d[i][j],d[i-1][j-v]w);}}}System.out.println(d[n][c]);}
}
思路三用一维数组实现
import java.util.Scanner;class Main {Scanner in new Scanner(System.in);static int[] w, v, d;static int n, c;public static void main(String[] args) {/*v为背包容量 n为物品件数*/n in.nextInt();c in.nextInt();w new int[n1];v new int[n1];d new int[c1];/*w为物品重量数组 v为物品价值数组*/for (int i 1; i n; i) {w[i] in.nextInt();v[i] in.nextInt();}for(int i 1; i n; i) {//一维数组实现二次循环中必须用倒序for(int j c; j w[i]; j--) {d[j] Math.max(d[j], d[j - w[i]] v[i]);}}System.out.println(d[c]);}
}思路四最简单版
import java.util.Scanner;public class Main {static Scanner in new Scanner(System.in);static int[] v, w, d;static int n, c;public static void main(String[] args) {n in.nextInt();c in.nextInt();v new int[n1];w new int[n1];d new int[c1];for (int i 1; i n; i) {int v in.nextInt();int w in.nextInt();for (int j c; j 0; j--) {if (j v) {d[j] Math.max(d[j], d[j-v] w);}}}System.out.println(d[c]);}
}
完全背包
用二维数组实现
import java.util.Scanner;class Main {public static void main(String[] args) {Scanner input new Scanner(System.in);/*v为背包容量 n为物品件数*/int v input.nextInt();int n input.nextInt();int[] weight new int[n1];int[] value new int[n1];int[][] fa new int[n1][v1];/*weight为物品重量数组 value为物品价值数组*/for (int i 1; i n; i) {weight[i] input.nextInt();value[i] input.nextInt();}for(int i 1; i n; i) {for(int j 1; j v; j) {for(int k 0; k * weight[i] j; k) {fa[i][j] Math.max(fa[i][j], fa[i - 1][j - k * weight[i]] k * value[i]);}}}System.out.println(fa[n][v]);}
}
用一维数组实现
import java.util.Scanner;class Main {public static void main(String[] args) {Scanner input new Scanner(System.in);/*v为背包容量 n为物品件数*/int v input.nextInt();int n input.nextInt();int[] weight new int[n1];int[] value new int[n1];int[] fa new int[v1];/*weight为物品重量数组 value为物品价值数组*/for (int i 1; i n; i) {weight[i] input.nextInt();value[i] input.nextInt();}for(int i 1; i n; i) {//完全背包问题一维数组实现二次循环必须正序for(int j weight[i]; j v; j) {fa[j] Math.max(fa[j], fa[j - weight[i]] value[i]);}}System.out.println(fa[v]);}
}
多重背包
用二维数组实现
import java.util.Scanner;class Main {public static void main(String[] args) {Scanner input new Scanner(System.in);/*v为背包容量 n为物品件数*/int v input.nextInt();int n input.nextInt();int[] weight new int[n1];int[] value new int[n1];int[] num new int[n1];int[][] fa new int[n1][v1];/*weight为物品重量数组 value为物品价值数组*/for (int i 1; i n; i) {weight[i] input.nextInt();value[i] input.nextInt();num[i] input.nextInt();}for(int i 1; i n; i) {for(int j 1; j v; j) {for(int k 1; k num[i] k * weight[i] j; k) {fa[i][j] Math.max(fa[i-1][j], fa[i - 1][j - k * weight[i]] k * value[i]);}}}System.out.println(fa[n][v]);}
}
用一维数组实现
import java.util.Scanner;class Main {public static void main(String[] args) {Scanner input new Scanner(System.in);/*v为背包容量 n为物品件数*/int v input.nextInt();int n input.nextInt();int[] weight new int[n1];int[] value new int[n1];int[] num new int[n1];int[] fa new int[v1];/*weight为物品重量数组 value为物品价值数组*/for (int i 1; i n; i) {weight[i] input.nextInt();value[i] input.nextInt();num[i] input.nextInt();}for (int i 1; i n; i) {for (int j v; j 1; j--) {for (int k 1; k num[i] k * weight[i] j; k) {fa[j] Math.max(fa[j], fa[j - k * weight[i]] k * value[i]);}}}System.out.println(fa[v]);}
}
