网站策划书模板,最近时事热点新闻评论及点评,最好的网站排名优化工作室,简述网站建设基本流程图问题描述#xff1a;
使用穷举法解决0/1背包问题。问题描述#xff1a;给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn} 的物品和一个容量为C的背包#xff0c;求这些物品中的一个最有价值的子集#xff0c;且要能够装到背包中。 穷举法#xff1a;每件物品装还是…问题描述
使用穷举法解决0/1背包问题。问题描述给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn} 的物品和一个容量为C的背包求这些物品中的一个最有价值的子集且要能够装到背包中。 穷举法每件物品装还是不装有两种选择使用0-表示不装1表示装n件物品就有2^n种穷举2^n种找到符合符合weight背包容量的且为价值最大的方式。
public class Main01 {//穷举法public void pack01(int weight,int[] wt,int[] val){int n wt.length;int count (int) Math.pow(2,n);int maxVal 0;//枚举32种情况并且记录符合weight重量背包的最大价值for (int i 0; i count; i) {String res String.format(%5s,Integer.toBinaryString(i)).replace( ,0);System.out.print(res );int sumVal 0;int sumWeight0;for (int j 0; j n; j) {//为1时表示装该物品 0表示不准装if (res.charAt(j)1) {sumVal val[j];sumWeight wt[j];}if (sumWeightweight){maxVal Math.max(sumVal,maxVal);}}System.out.println(价值sumVal重量sumWeight);}//打印最大价值下对应的背包实际重量和所装物品的状态for (int i 0; icount; i) {String res String.format(%5s,Integer.toBinaryString(i)).replace( ,0);int sumVal 0;int sumWeight0;for (int j 0; j n; j) {if (res.charAt(j)1) {sumVal val[j];sumWeight wt[j];}}if (sumValmaxValsumWeightweight){System.out.println(当背包重量为weight时最大价值:sumVal 总重量 sumWeight 方式res);break;}}}public static void main(String[] args) {Main01 main01 new Main01();int[] wt {1, 2, 1, 12, 4};int[] val {1, 2, 2, 4, 10};main01.pack01(15, wt, val);}
} 输出结果 二维dp数组
dp[i][w]数组含义对于前i个物品当前背包容量为w时可装下的最大值是dp[i][w]。 dp[i-1][w-wt[i-1]]val[i-1]装物品i的价值 dp[i-1][w]不装物品i的价值 因此dp[i][w]取装物品 i dp[i-1][w-wt[i-1]]val[i-1] 和 不装物品i dp[i-1][w] 的最大值
public class Main01 {public static void main(String[] args) {int[] wt {1, 2, 1, 12, 4};int[] val {1, 2, 2, 4, 10};int res pack01(15,wt,val);System.out.println(最大价值res);}public static int pack01(int weight,int[] wt,int[] val){int n wt.length;//dp[i][w]数组含义对于前i个物品当前背包容量为w时可装下的最大值是dp[i][w]int[][] dp new int[n1][weight1];for (int i 1; i n; i) {for (int w 1; w weight; w) {if (wt[i-1]w){//不能装入背包dp[i][w] dp[i-1][w];}else {//择优装入背包dp[i][w] Math.max(dp[i-1][w-wt[i-1]]val[i-1],dp[i-1][w]);}}}//打印dp表for (int i 0; i n ; i) {for (int j 0; j weight ; j) {if (jweight){System.out.print(dp[i][j],);}else {System.out.print(dp[i][j]);}}System.out.println();}return dp[n][weight];}
}输出结果
