Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 1 KB
using System;
namespace Teher
{
class Program
{
const string InpFile = "teher.be",
OutFile = "teher.ki";
private int N, kapacitas;
private int[] sulyok, fizetseg;
private int[,] cache;
private bool[,] choice;
private void ReadValues(string line, ref int a, ref int b)
{
string[] sor = line.Split();
a = Convert.ToInt32(sor[0]);
b = Convert.ToInt32(sor[1]);
}
private void Betolt()
{
System.IO.StreamReader sr = new System.IO.StreamReader(InpFile);
ReadValues(sr.ReadLine(), ref N, ref kapacitas);
sulyok = new int[N]; fizetseg = new int[N];
cache = new int[N + 1, kapacitas + 1]; choice = new bool[N, kapacitas + 1];
for (int i = 0; i < N; i++) {
ReadValues(sr.ReadLine(), ref fizetseg[i], ref sulyok[i]);
}
for (int i = 0; i <= N; i++)
for (int j = 0; j <= kapacitas; j++)
cache[i, j] = -1;
sr.Close();
}
private int Legjobb(int hely, int marad)
{
int ertek1 = 0, ertek2 = 0;
if (cache[hely, marad] == -1) {
if (hely == N)
cache[hely, marad] = 0;
else {
ertek1 = Legjobb(hely + 1, marad);
choice[hely, marad] = false;
if (marad >= sulyok[hely]) {
ertek2 = fizetseg[hely] + Legjobb(hely + 1, marad - sulyok[hely]);
if (ertek2 > ertek1)
choice[hely, marad] = true;
}
cache[hely, marad] = ertek1 > ertek2 ? ertek1 : ertek2;
}
}
return cache[hely, marad];
}
private void Kiir()
{
int marad = kapacitas;
System.IO.StreamWriter sw = new System.IO.StreamWriter(OutFile);
sw.WriteLine(Legjobb(0, kapacitas));
for (int i = 0; i < N; i++)
if (choice[i, marad]) {
sw.WriteLine(i + 1);
marad -= sulyok[i];
}
sw.Close();
}
public static void Main(string[] args)
{
Program program = new Program();
program.Betolt();
program.Kiir();
}
}
}
