With these two arrays, the indexes of capacity correspond with price.

int[] price = {60, 120, 100 , 100, 30 , 20};
int[] capacity = {1, 3, 2 , 2, 3 , 1};

I wish to find the maximum total price possible with a capacity restriction.

The function would be func(price,capacity,capacityRestriction)

Calling func(price,capacity,6)
would return 280 because 280 is the highest possible amount we can get with 6 being the capacity limit. 

CodePudding user response：

Given the data you outlined above I believe your answer should be 280.

To find the solution you need to first determine the price density at each index by dividing the price by the capacity. Then you fill your total allowed capacity by attempting to select the item with the highest price density remaining. If that item does not fit in the remaining capacity you just move on to the item with the next highest capacity.

In java, sticking to using only primitives and primitive arrays:

public class Main {

  public static void main(String[] args) {
    int[] price = {60, 120, 100, 100, 30, 20};
    int[] capacity = {1, 3, 2, 2, 3, 1};
    final int totalPrice = maximizePriceForCapacity(price, capacity, 6);
    System.out.printf("Total price=%d\n", totalPrice);
  }

  public static int maximizePriceForCapacity(int[] prices, int[] capacities, int totalCapacity) {
    assert prices.length == capacities.length;

    int arraySizes = prices.length;
    // first we figure out the price per capacity unit
    float[] priceDensities = new float[arraySizes];
    for (int i = 0; i < arraySizes; i   ) {
      priceDensities[i] = (float) prices[i] / (float) capacities[i];
    }

    // then we select items starting with the item which has the highest price per capacity
    // and continuing to towards items which have a lesser price per capacity until we fulfill
    // the total capacity or reach a point where capacity can not be fulfilled.  At any step if
    // an items capacity is too large to fit we move on to the item with the next highest price
    // capacity

    int selectedCapacity = 0;
    int totalPrice = 0;
    boolean[] completedIndexes = new boolean[arraySizes];
    while(selectedCapacity < totalCapacity) {
      float highestPriceDensitySeen = 0;
      int selectedIndex = -1;
      for (int i = 0; i < arraySizes; i   ) {
        if (completedIndexes[i]) {
          // we already selected or ruled out this index, just continue to the next
          continue;
        }
        float currentPriceDensity = priceDensities[i];
        if (currentPriceDensity > highestPriceDensitySeen) {
          highestPriceDensitySeen = currentPriceDensity;
          selectedIndex = i;
        }
      } // end for loop
      if (selectedIndex == -1) {
        // no more items are available for selection
        break;
      }
      // mark our selectedIndex as completed
      completedIndexes[selectedIndex] = true;
      int itemPrice = prices[selectedIndex];
      int itemCapacity = capacities[selectedIndex];
      // we selected our best candidate for the next item... check if it fits
      if (selectedCapacity   itemCapacity > totalCapacity) {
        // this item does not fit...
        continue;
      }
      // this item fits, add it to the totals
      selectedCapacity  = itemCapacity;
      totalPrice  = itemPrice;
      System.out.printf("Selecting item at index=%d, with capacity=%d and price=%d.\n", selectedIndex, itemCapacity, itemPrice);
      System.out.printf("\tselectedCapacity=%d, totalPrice=%d\n", selectedCapacity, totalPrice);
    } // end while loop
    return totalPrice;
  }
}

Output:

Selecting item at index=0, with capacity=1 and price=60.
    selectedCapacity=1, totalPrice=60
Selecting item at index=2, with capacity=2 and price=100.
    selectedCapacity=3, totalPrice=160
Selecting item at index=3, with capacity=2 and price=100.
    selectedCapacity=5, totalPrice=260
Selecting item at index=5, with capacity=1 and price=20.
    selectedCapacity=6, totalPrice=280
Total price=280