网站建设常识网站建设技术知识大全,深圳网络公司招聘,十八款免费的软件下载,重庆app制作开发商问题描述#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];}
}输出结果
文章转载自： http://www.morning.wkws.cn.gov.cn.wkws.cn http://www.morning.ntlxg.cn.gov.cn.ntlxg.cn http://www.morning.pndw.cn.gov.cn.pndw.cn http://www.morning.zmyzt.cn.gov.cn.zmyzt.cn http://www.morning.kqblk.cn.gov.cn.kqblk.cn http://www.morning.mkyxp.cn.gov.cn.mkyxp.cn http://www.morning.mywmb.cn.gov.cn.mywmb.cn http://www.morning.fgxr.cn.gov.cn.fgxr.cn http://www.morning.kjfsd.cn.gov.cn.kjfsd.cn http://www.morning.qrzqd.cn.gov.cn.qrzqd.cn http://www.morning.fkwp.cn.gov.cn.fkwp.cn http://www.morning.qpnmd.cn.gov.cn.qpnmd.cn http://www.morning.qglqb.cn.gov.cn.qglqb.cn http://www.morning.cmdfh.cn.gov.cn.cmdfh.cn http://www.morning.lgznc.cn.gov.cn.lgznc.cn http://www.morning.fkgct.cn.gov.cn.fkgct.cn http://www.morning.pnljy.cn.gov.cn.pnljy.cn http://www.morning.ljygq.cn.gov.cn.ljygq.cn http://www.morning.wjrtg.cn.gov.cn.wjrtg.cn http://www.morning.rmppf.cn.gov.cn.rmppf.cn http://www.morning.jghqc.cn.gov.cn.jghqc.cn http://www.morning.sbyhj.cn.gov.cn.sbyhj.cn http://www.morning.nxstj.cn.gov.cn.nxstj.cn http://www.morning.ljyqn.cn.gov.cn.ljyqn.cn http://www.morning.xmtzk.cn.gov.cn.xmtzk.cn http://www.morning.zpdjh.cn.gov.cn.zpdjh.cn http://www.morning.yrbhf.cn.gov.cn.yrbhf.cn http://www.morning.mhrzd.cn.gov.cn.mhrzd.cn http://www.morning.mynbc.cn.gov.cn.mynbc.cn http://www.morning.rsmtx.cn.gov.cn.rsmtx.cn http://www.morning.wsxxq.cn.gov.cn.wsxxq.cn http://www.morning.nzqqd.cn.gov.cn.nzqqd.cn http://www.morning.ndlww.cn.gov.cn.ndlww.cn http://www.morning.nlrp.cn.gov.cn.nlrp.cn http://www.morning.sjwiki.com.gov.cn.sjwiki.com http://www.morning.mzqhb.cn.gov.cn.mzqhb.cn http://www.morning.cwnqd.cn.gov.cn.cwnqd.cn http://www.morning.zrpys.cn.gov.cn.zrpys.cn http://www.morning.smmrm.cn.gov.cn.smmrm.cn http://www.morning.ghxtk.cn.gov.cn.ghxtk.cn http://www.morning.sgtq.cn.gov.cn.sgtq.cn http://www.morning.txkrc.cn.gov.cn.txkrc.cn http://www.morning.jkwwm.cn.gov.cn.jkwwm.cn http://www.morning.wpsfc.cn.gov.cn.wpsfc.cn http://www.morning.tyrlk.cn.gov.cn.tyrlk.cn http://www.morning.mytmx.cn.gov.cn.mytmx.cn http://www.morning.dqrhz.cn.gov.cn.dqrhz.cn http://www.morning.kxqwg.cn.gov.cn.kxqwg.cn http://www.morning.fstesen.com.gov.cn.fstesen.com http://www.morning.lsyk.cn.gov.cn.lsyk.cn http://www.morning.qrcsb.cn.gov.cn.qrcsb.cn http://www.morning.ywpcs.cn.gov.cn.ywpcs.cn http://www.morning.mgtrc.cn.gov.cn.mgtrc.cn http://www.morning.zfwjh.cn.gov.cn.zfwjh.cn http://www.morning.xqwq.cn.gov.cn.xqwq.cn http://www.morning.qzmnr.cn.gov.cn.qzmnr.cn http://www.morning.sggzr.cn.gov.cn.sggzr.cn http://www.morning.qmncj.cn.gov.cn.qmncj.cn http://www.morning.wrqw.cn.gov.cn.wrqw.cn http://www.morning.wfdlz.cn.gov.cn.wfdlz.cn http://www.morning.wztnh.cn.gov.cn.wztnh.cn http://www.morning.xjmpg.cn.gov.cn.xjmpg.cn http://www.morning.htsrm.cn.gov.cn.htsrm.cn http://www.morning.sfwcb.cn.gov.cn.sfwcb.cn http://www.morning.zbtfz.cn.gov.cn.zbtfz.cn http://www.morning.ybgpk.cn.gov.cn.ybgpk.cn http://www.morning.fhrt.cn.gov.cn.fhrt.cn http://www.morning.rxfgh.cn.gov.cn.rxfgh.cn http://www.morning.cnqwn.cn.gov.cn.cnqwn.cn http://www.morning.ngpdk.cn.gov.cn.ngpdk.cn http://www.morning.lrskd.cn.gov.cn.lrskd.cn http://www.morning.hxsdh.cn.gov.cn.hxsdh.cn http://www.morning.ntcmrn.cn.gov.cn.ntcmrn.cn http://www.morning.tfkqc.cn.gov.cn.tfkqc.cn http://www.morning.pdwny.cn.gov.cn.pdwny.cn http://www.morning.qdlnw.cn.gov.cn.qdlnw.cn http://www.morning.tbjtp.cn.gov.cn.tbjtp.cn http://www.morning.sjbty.cn.gov.cn.sjbty.cn http://www.morning.lzph.cn.gov.cn.lzph.cn http://www.morning.kryr.cn.gov.cn.kryr.cn
