题解 | #字符串最后一个单词的长度#

首先，给定的物品之间存在从属关系，所以如果把附件不单独看成物品而归类开主件中的话，那么主件的价格和重要度就可能各存在4种情况（光主件，主件加附件1，主件加附件2，主件加附件1和2）。 我们把主件及及可选附件算成一件完成的物品(class good)，存在4个price变量和4个value变量(value=price 乘 重要度) main函数中除最后一行外就是在构建一个good数组。

最后关于给定的物品在给定的金钱限定下得到的价值最优解，由getMaxValue(good[] gds,int money)实现。 这个问题本质上是0-1背包问题（背包容量即为金钱限额）。网上有很多关于它的笔记，我这里说下我认为的最通俗的理解方法。

这里构建一个二维数组tmp[][],第一个维度代表物品维度，第二个维度代表金钱维度。 其实物品维度中，各个物品的排序顺序随意确定即可，这里就按输入顺序来就行。 为理解方便，tmp[0][j]表示一个物品都没有的情况下，背包容量为j时，可装下的最大价值，很显然应该为0； 同理，tmp[i][0]表示背包容量为0的情况下，存在i个物品可供挑选时，可装下的最大价值，很明显也应该为0； tmp[i][j]表示：在前i个物品可选，且背包容量为j时，可装下的最大价值。 其取值逻辑为： 1.如果第i个物品的4个价值有<=背包容量j的，那就需要尝试着将它放入背包，看看是否比不放入的时候价值大。 2.如果不放入，则tmp[i][j]=tmp[i-1][j],就是说跟没见到第i个物品，背包容量为j时记录的最大价值一样 3.如果放入，则要考虑放哪一种组合。 假定该物品某个价格为price,价值为value，如果要放入这个物品，最起码要让背包空出price的空间，因此，我们可以用 tmp[i-1][j-price]的值+value来求得放入后的总价值， 其中tmp[i-1][j-price]表示前i-1个物品出现，且背包容量为j-price的最大容量。 4.4种价格依次尝试后的4个价值外加不放入时tmp[i-1][j]，这5个值中求最大值，即为tmp[i][j]的最大值，记录到数组元素中 5.tmp[实际物品数][最大金钱数]即为我要的最终解。

代码如下： import java.util.*;

public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int money = sc.nextInt(); int count = sc.nextInt(); HashMap<Integer,Integer> fjPrice=new HashMap<Integer,Integer>(); HashMap<Integer,Integer> fjValue=new HashMap<Integer,Integer>(); good[] gds = new good[count]; for(int i = 0; i < count; i++){ int price = sc.nextInt(); int value = price*sc.nextInt(); int belong = sc.nextInt(); if(belong == 0){//如果是主件，第几个进来就放到对应下标i的元素中 if(gds[i]!=null) {//如果对象已经存在，把主件的信息录入进去，否则直接以附件信息生成对象 gds[i].setMainV_P(price,value); }else{ gds[i] = new good(price, value, 1); } }else{//否则记录到belong-1下标的元素中 if(gds[belong-1]!=null){//如果对象已经存在，把附件的信息录入进去，否则直接以附件信息生成对象 gds[belong-1].setAllV_P(price,value); }else{ gds[belong-1]=new good(price,value,0); } } } ArrayList agds = new ArrayList(); for(good gd:gds){ if(gd != null){ agds.add(gd); } } gds = new good[agds.size()]; for(int i=0;i<agds.size();i++){ gds[i]=agds.get(i); } System.out.println(getMaxValue(gds,money)); } public static int getMaxValue(good[] gds,int money){ int[][] tmp = new int[gds.length+1][money+1]; for(int i = 0;i<=gds.length;i++){ tmp[i][0]=0; } for(int j=0;j<=money;j++){ tmp[0][j]=0; } for(int i = 1;i<=gds.length;i++){ for(int j=1;j<=money;j++){//判断每个tmp[i][j]的最大值 //如果gds[i]的4个价格有存在<=j的情况，才会考虑要不要把这个物品放入背包 int value0=0; int valueWith1=0; int valueWith2=0; int valueWithAll=0; if(gds[i-1].price0<=j){ value0 = tmp[i-1][j-gds[i-1].price0]+gds[i-1].value0; } if(gds[i-1].priceWith1<=j){ valueWith1 = tmp[i-1][j-gds[i-1].priceWith1]+gds[i-1].valueWith1; } if(gds[i-1].priceWith2<=j){ valueWith2 = tmp[i-1][j-gds[i-1].priceWith2]+gds[i-1].valueWith2; } if(gds[i-1].priceWithAll<=j){ valueWithAll = tmp[i-1][j-gds[i-1].priceWithAll]+gds[i-1].valueWithAll; } tmp[i][j]=Math.max(Math.max(Math.max(Math.max(tmp[i-1][j],value0),valueWith1),valueWith2),valueWithAll); //System.out.print(tmp[i][j]+" "); } //System.out.println(); } return tmp[gds.length][money]; } public static class good{ public int price0=0; public int priceWith1=0; public int priceWith2=0; public int priceWithAll=0; public int value0=0; public int valueWith1=0; public int valueWith2=0; public int valueWithAll=0; public good(int price,int value,int flag){ if(flag ==1) {//flag=1表示以主件信息构建物品 this.price0 = price; this.priceWith1 = price; this.priceWith2 = price; this.priceWithAll = price; this.value0 = value; this.valueWith1 = value; this.valueWith2 = value; this.valueWithAll = value; }else{ setAllV_P(price,value); } } public void setAllV_P(int price,int value){ if(valueWith1==value0){//第一个附件进来的时候设置valueWith1和valueWithAll,priceWith1和priceWithAll valueWith1+=value; valueWithAll+=value; priceWith1+=price; priceWithAll+=price; }else if(valueWith2==value0){//第二个附件进来时，设置valueWith2和valueWithAll,priceWith2和priceWithAll valueWith2+=value; valueWithAll+=value; priceWith2+=price; priceWithAll+=price; } } public void setMainV_P(int price,int value){ this.price0 += price; this.priceWith1 += price; this.priceWith2 += price; this.priceWithAll += price; this.value0 += value; this.valueWith1 += value; this.valueWith2 += value; this.valueWithAll += value; } } }