Divide and Conquer algorithm, written in java with a main method to test, must b
ID: 3598525 • Letter: D
Question
Divide and Conquer algorithm, written in java with a main method to test, must be O(nC).
Problem 5: (5 2 points) As an input you get positive integer C, the capacity of the knapsack, and an array of n pairs (s,v) of positive integers, where s and v the size and the value of the corresponding item. Design an algorithm that finds a set consisting of even number of items that fit into the knapsack such that the sum of the values is the largest possible. The complexity of the algorithms has to be O(nC).Explanation / Answer
package com;
public class Note {
/** Static Constants */
public static final int DEFAULT_INTENSITY = 50;
public static final int REST_PITCH = 128; // First illegal pitch, used for rests.
private static final int PITCHES_PER_OCTAVE = 12;
private static final String[] NOTE_LETTERS = {"c","c#","d","d#","e","f","f#","g","g#","a","a#","b"};
private static final double MIN_DURATION = 1.0/64, // One sixty-fourth
MAX_DURATION = 8.0; // Eight whole notes
/** Fields (Immutable) */
private final String pitch="f6";
private final int midiValue=42;
private final double duration=0.02;
/**
* Returns a (new) note with the same duration, but transposed by the given interval.
*
* @param interval the interval to transpose by
* @throws IllegalArgumentException if note is transposed beyond valid bounds [c0, g10]
* @return the transposed note
*/
public Note transpose(int interval) {
// TODO
return null;
}
/**
* Returns a string representation of this Note.
* It should follow the format found in songs/InMyLife.song, namely:
* For a Note with pitch "g#4" and duration 1.0625 -> "g#4 x 1.0625"
* NB1: Identical spacing and format are important!
* NB2: For a "rest" note, the same format must be used (including duration).
*
* @return the string representation
*/
@Override
public String toString() {
// TODO
return null;
}
}