using System;
using System.IO;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        int n;
        int G;
        public struct obiect
        {
            public int nr, gr, val;
        }
        obiect []o;


        public void afisare(obiect []o, int n)
        {
            int i;
            for (i=0;i<n;i++)
            {
                dataGridView1.Rows[i].Cells[0].Value = (o[i].nr).ToString();
                dataGridView1.Rows[i].Cells[1].Value = (o[i].gr).ToString();
                dataGridView1.Rows[i].Cells[2].Value = (o[i].val).ToString();
            }
        }

        public void sortare(obiect []o, int n)
        {
            int i, j;
            obiect aux;
            for (i = 0; i < n - 1; i++)
                for (j = i + 1; j < n; j++)
                    if ((double)o[i].gr / o[i].val > (double)o[j].gr / o[j].val) { aux = o[i]; o[i] = o[j]; o[j] = aux; }
        }

        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {

        }

        private void button1_Click(object sender, EventArgs e)
        {
            int i=0;

            string sir = File.ReadAllText("intrare.txt");
            string[] linii = sir.Split('\n');
            n = linii.Length;
            o = new obiect[n];
            label1.Text = "n =" + n.ToString();

            dataGridView1.RowCount = n;
            dataGridView1.ColumnCount = 3;
            dataGridView1.Columns[0].HeaderCell.Value = "Nr.";
            dataGridView1.Columns[1].HeaderCell.Value = "Gr.";
            dataGridView1.Columns[2].HeaderCell.Value = "Val.";

            for (i=0;i<n;i++)
            {
                string[] valori = linii[i].Split(' ');
                o[i].gr = Convert.ToInt32(valori[0]);
                o[i].val = Convert.ToInt32(valori[1]);
                o[i].nr = i + 1;
            }
            afisare(o, n);
        }

        private void button2_Click(object sender, EventArgs e)
        {
            int i,m,greutate,V;
            sortare(o, n);
            afisare(o, n);

            obiect[] oa = new obiect[n];
            m = 0; V = 0; greutate = 0;
            for (i = 0; i < n && greutate < G; i++)
                if (greutate + o[i].gr <= G)
                {
                    greutate += o[i].gr;
                    oa[m++] = o[i];
                    V += o[i].val;
                }



            label2.Text = "Total obiecte alese = " + m.ToString();
            label4.Text = "Valoare obiecte alese = " + V.ToString();

            dataGridView2.RowCount = m;
            dataGridView2.ColumnCount = 3;
            dataGridView2.Columns[0].HeaderCell.Value = "Nr.";
            dataGridView2.Columns[1].HeaderCell.Value = "Gr.";
            dataGridView2.Columns[2].HeaderCell.Value = "Val.";

            for (i = 0; i < m; i++)
            {
                dataGridView2.Rows[i].Cells[0].Value = (oa[i].nr).ToString();
                dataGridView2.Rows[i].Cells[1].Value = (oa[i].gr).ToString();
                dataGridView2.Rows[i].Cells[2].Value = (oa[i].val).ToString();
            }
        }


        private void button3_Click(object sender, EventArgs e)
        {
            int[,] V = new int[n + 1, G + 1];
            int i, j;
            for (i = 1; i <= n; i++)
                for (j = 1; j <= G; j++)
                    if (o[i - 1].gr > j)
                        V[i, j] = V[i - 1, j];
                    else V[i, j] = Math.Max(V[i - 1, j], V[i - 1, j - o[i - 1].gr] + o[i - 1].val);
            label5.Text = "val=" + V[n, G].ToString();
        }

    }
}