public class Dtgh { public static int maxWeight = 80; public static String[] wpName = {"1","2","3","4","5","6"};//物品名称 public static int[] weightArr = {10,15,20,25,30,35};//每个物品的重量 public static int[] priceArr = {15,25,35,45,55,70};//每个物品的价值 public static int[][] resultJz = new int[6][80/5];//动态规划结果集 每格5kg 80可以画16个格子 /** * 背包问题，同一个物品可以放一次 递归 有重复计算的问题 * @param num 剩余可选物品 * @param weight 剩余可放重量 * @return */ public static int backpack(int num,int weight){ int size = wpName.length; if(num==0||weight==0){ return 0; } int result =0; if(weight<weightArr[size-num]){ result = backpack(num-1,weight); //System.out.println("剩余物品数："+num+"** 剩余重量："+weight+"**总价值："+result); return result; } int val1 = backpack(num-1,weight-weightArr[size-num])+priceArr[size-num]; int val2 = backpack(num-1,weight); if(val1>=val2){ System.out.println("添加物品名称："+wpName[size-num]+"** 剩余重量："+weight+"**总价值："+result); } result = Math.max(val1,val2);
return result; }
public static int backpack(){ int result =0; for(int i=0;i<=wpName.length;i++){ for(int j=0;j<resultJz[0].length;j++){ if(i==0){ resultJz[i][j] = 0; }else if(j==0){ resultJz[i][j] = 0; }else{ if(j*5<weightArr[i-1]){//当前格剩余重量小于物品重量 resultJz[i][j] = resultJz[i-1][j] ; }else{ resultJz[i][j] = Math.max(resultJz[i-1][j],resultJz[i-1][j-(weightArr[i-1]/5)]+priceArr[i-1]); } } System.out.print(resultJz[i][j]+","); } System.out.println(); }
result = resultJz[wpName.length][resultJz[0].length-1]; return result; }
public static void main(String[] args) { //int result = backpack(wpName.length, maxWeight); int result = backpack(); System.out.println(result); }}
评论