Rapasoft.eu

/**
 * @author rapasoft
 * 
 * Majme n predmetov (z kazdeho je jeden kus), ktorych velkosti su
 * velkosti[1]..velkosti[n] a a ceny su ceny[1]..ceny[n], a batoh o kapacite m.
 * Zistite sumu predmetov, ktore mozno odniest v batohu tak, aby platilo, ze
 * suma cien predmetov v batohu je maximalna a suma velkosti predmetov v batohu
 * je mensia ako m.
 * 
 */
public class Knapsack {

	final static int m = 10; // kapacita batohu

	final static int n = 5; // pocet veci v trezore

	public static void main(String[] args) {
		int[] ceny = new int[n + 1];
		int[] velkosti = new int[n + 1];
		int sumacien = 0;
		for (int i = 0; i < n + 1; i++) {
			if (i != 0) {
				ceny[i] = (int) (Math.random() * 4 + 1);
				velkosti[i] = (int) (Math.random() * 9 + 1);
				System.out.println(i + ".: Cena: " + ceny[i] + ", Velkost: ("
						+ velkosti[i] + ")");
				sumacien += ceny[i];
			}
			// nultu hodnotu nechame prazdnu
			else {
				ceny[i] = 0;
				velkosti[i] = 0;
			}
		}
		System.out.println("Suma cien:" + sumacien);
		System.out.println("----------------------------------");
		// Vybudovanie ciastocnych rieseni:
		int[][] c = new int[n + 1][m + 1]; // pociatocny stav pola su same nuly
		// zaciname od indexu 1
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < m + 1; j++) {
				if (velkosti[i] > j)// ak je velkost i-teho predmetu vacsia ako
					// j
					c[i][j] = c[i - 1][j]; // uloz predchadzajuce riesenie
				else {
					c[i][j] = Math.max(c[i - 1][j], (ceny[i] + c[i - 1][j
							- velkosti[i]]));
					/*
					 * uloz maximum z predchadzajucej hodnoty a "magickeho
					 * vzorca": cena i-teho predmetu + hodnota pomocneho vypoctu
					 * predchadzajuceho predmetu s velkostou znizenou o velkost
					 * pridavaneho predmetu.
					 */
				}
			}
		}
		System.out.println("Najvyssia mozna suma, ktora sa da zobrat: "
				+ c[n][m]);
	}
}