首页 > 代码库 > 蓝桥杯——说好的进阶之完全背包问题
蓝桥杯——说好的进阶之完全背包问题
有N种物品和一个载重量为W的背包,每种物品都有无限件可用。第i种物品的重量是w,价值是p。将哪些物品装入背包可使这些物品的重量总和不超过背包总重量,且价值总和最大。(对比01背包问题,取或不取与无限件)
static int W=10; static int[] w_arr = new int[]{3,2,5,1,6,4}; static int[] p_arr = new int[]{6,5,10,2,16,8}; static int[][] v; public static void main(String[] args) { // TODO Auto-generated method stub v=new int[w_arr.length+1][W+1]; //法一 cal(); //改进 k(); } static void k() { int[] b=new int[W+1]; for(int i=0;i<w_arr.length;i++) { for(int j=w_arr[i];j<=W;j++) //第 i 件取入影响最优解 正向以充分考虑 { b[j]=Math.max(b[j], b[j-w_arr[i]]+p_arr[i]); } } for(int i:b) { System.out.print(i+" "); } System.out.println(); System.out.println(b[W]); } static void cal() { for(int i=1;i<v.length;i++) { for(int j=1;j<v[0].length;j++) { for(int k=0;k<=j/w_arr[i-1];k++) { v[i][j]=Math.max(v[i-1][j],v[i-1][j-k*w_arr[i-1]]+k*p_arr[i-1]); } } } for(int i[]:v) { for(int j:i) { System.out.print(j+" "); } System.out.println(); } System.out.println(v[w_arr.length][W]); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。