Java sort排序

Question

import java.util.*;

public class HW7 {

  public static void main(String[] args) {
    // Q1
    //System.out.println(bestValue(7, new int[] {}, new int[] {})); // 0
    //System.out.println(bestValue(7, new int[] {4}, new int[] {1})); // 4
    System.out.println(bestValue(7, new int[] {4, 10, 2, 4}, new int[] {3, 1, 5, 2})); // 24
    System.out.println(bestValue(7, new int[] {4, 10, 2, 4}, new int[] {3, 3, 5, 2})); // 25
    System.out.println(bestValue(7, new int[] {4, 10, 2, 4}, new int[] {3, 5, 5, 2})); // 35
  }

  public static int bestValue(int W, int[] counts, int values[]) {
    MetalBar[] bars = new MetalBar[counts.length];
    System.out.println(Arrays.toString(bars));
    for(int i = 0; i < counts.length; i++){
      bars[i] = new MetalBar(values[i],counts[i]);
    }
    Arrays.sort(bars);
    System.out.println(Arrays.toString(bars));
    int sum = 0;
    int [] R = new int [counts.length];//make a new list 
    for(int i=0;i<=counts.length;i++){//for loop from 0 to length i
      if(counts[i]<=W){//if count i smaller than W
        R[i]=counts[i];//add counts[i] to R list as index 0 then
        W-=counts[i];//renew W minus by count[i]
      }
      else if(W>=0){//in the least step counts[i]is greater than W but it is still not compelete
        R[i]=W;//the least index of R will be fill by the remain number of W.
        break;
      }
      else{
        break;
      }  
    }
    for(int i=0;i<R.length;i++){//from 0 to R.length
      sum+= R[i]*values[i];//muplti R and Values to get to total number of the bag value
    }
    return sum;
  }
}

import java.util.*;

public class MetalBar implements Comparable<MetalBar> {

  private int value;
  private int count;

  public MetalBar(int value, int count) {
    this.value = value;
    this.count = count;
  }

  public int getValue() {
    return value;
  }

  public int getCount() {
    return count;
  }

  // Compare based on value
  public int compareTo(MetalBar otherBar) {
    return Integer.compare(otherBar.value, value);
  } 

  public String toString() {
    return String.format("MetalBar(%d, %d)", value, count);
  }

}

Q1: Treasure Cave (3 points)
Imagine you find a hidden cave filled with with N different types of metal bars (gold, silver, platinum, steel, etc.) Each type of metal bar has some value vi, and there are xi bars of that metal in the cave (for i = 0, 1, 2, 3, ... N-1). You want to bring back as many bars as of the treasure as you can, but your bag can only fit W bars. How do you choose how many bars of each metal to bring home to maximize the total value?

For example, if your bag can store 7 bars and you have gold, silver, platinum, and steel in these quantities:

[4, 10, 2, 4] // 4 bars of gold, 10 silver, 2 platinum, 4 steel
and these values

[3, 1, 5, 2]  // gold worth 3 per bar, silver worth 1, platinum 5, steel 2
Then you would want to take this much of each metal

[4, 0, 2, 1]  // all the gold, no silver, all the platinum, 1 steel bar
              // for a total value of 24 (4*3 + 2*5 + 1*2)
Write bestValue() which takes in an integer W, an array of counts, and an array of values. It should return the best value you can earn by picking the bars optimally. Your code should run in O(nlogn).

Hint #1: This can be done using a Greedy approach.
Hint #2: We've provided MetalBar.java to help you out here. Check the homework party to see how to use it.

[4，10，2，4]//4金条，10银，2铂，4钢

这些价值观

[3，1，5，2]//每根金条价值3英镑，每根银条价值1英镑，每根白金5英镑，每根钢2英镑

那你就要把每种金属都拿走这么多

[4，0，2，1]//所有的黄金，没有白银，所有的铂金，1根钢筋

//总价值24（4*3+2*5+1*2）

现在有一个问题是最后一步不知道怎么用sort后的values 在图片里的bars[]内values

Answer 1

其实这道题很简单的，因为你这个背包只有数量限制，没有容量这一说法。所以你的思路是根据价值排序，然后直接取就好了。

public class Test {

  public static void main(String[] args) {
    // Q1
    //System.out.println(bestValue(7, new int[] {}, new int[] {})); // 0
    //System.out.println(bestValue(7, new int[] {4}, new int[] {1})); // 4
    System.out.println(bestValue(7, new int[] {4, 10, 2, 4}, new int[] {3, 1, 5, 2})); // 24
    System.out.println(bestValue(7, new int[] {4, 10, 2, 4}, new int[] {3, 3, 5, 2})); // 25
    System.out.println(bestValue(7, new int[] {4, 10, 2, 4}, new int[] {3, 5, 5, 2})); // 35
  }

  public static int bestValue(int W, int[] counts, int values[]) {
    MetalBar[] bars = new MetalBar[counts.length];
    for(int i = 0; i < counts.length; i++){
      bars[i] = new MetalBar(values[i],counts[i]);
    }
    Arrays.sort(bars);

    int sum = 0;
    // 根据价值从高到低，直到没有东西，或者背包已经满了
    for (int i = 0; i < bars.length && W > 0; i++) {
      MetalBar bar = bars[i];
      int num = Math.min(W, bar.getCount());
      sum += num * bar.getValue();
      W -= num;
    }

    return sum;
  }
}

class MetalBar implements Comparable<MetalBar> {

  private int value;
  private int count;

  public MetalBar(int value, int count) {
    this.value = value;
    this.count = count;
  }

  public int getValue() {
    return value;
  }

  public int getCount() {
    return count;
  }

  // Compare based on value
  public int compareTo(MetalBar otherBar) {
    return Integer.compare(otherBar.value, value);
  }

  public String toString() {
    return String.format("MetalBar(%d, %d)", value, count);
  }

}