۱۲-آذر-۱۳۹۲, ۲۳:۵۹:۴۱
کد:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication6
{
class Program
{
/// Cite http://daneshju-club.com if you want to use the source code
///writen by navid
static int W;
static decimal[] x;
static decimal[] p;
static decimal[] w;
static void Main(string[] args)
{
int n;
Console.WriteLine("enter number of elements:");
n = Convert.ToInt32(Console.ReadLine());
p = new decimal[50];
w = new decimal[50];
int i;
Console.WriteLine("enter the weight of elements:");
for (i = 0; i < n; i++)
w[i] = Convert.ToInt16(Console.ReadLine());
Console.WriteLine("enter the value of elements:");
for (i = 0; i < n; i++)
p[i] = Convert.ToInt16(Console.ReadLine());
Console.WriteLine("capacity of knapsock:");
W = Convert.ToInt16(Console.ReadLine());
Sort(p, w, n);
}
static void Sort(decimal[] p, decimal[] w, int n)
{
int i, j;
decimal temp;
for (i = 0; i < n; i++)
for (j = n - 1; j > i; j--)
{
if (p[j - 1] / w[j - 1] < p[j] / w[j])
{
temp = p[j - 1];
p[j - 1] = p[j];
p[j] = temp;
temp = w[j - 1];
w[j - 1] = w[j];
w[j] = temp;
}
}
knapsack(p, w, n);
}
static void knapsack(decimal[] p, decimal[] w, int n)
{
int i, flag = 1;
decimal cu, sum;
x = new decimal[n];
for (i = 0; i < n; i++)
x[i] = 0;
cu = W;
for (i = 0; (i < n) && (flag == 1); i++)
{
if (w[i] > cu)
flag = 0;
else
{
x[i] = 1;
cu = cu - w[i];
Console.WriteLine("the item with weight " + w[i] + " and value " + p[i] + " push to knapsack.");
}
}
if (flag == 0)
if (i <= n)
{
Console.WriteLine(cu + "/" + w[i - 1] + " item with weight " + w[i - 1] + " and value " + p[i - 1] + " push to knapsack.");
x[i - 1] = cu / w[i - 1];
}
Console.WriteLine("the value of the knapsack: ");
sum = 0;
for (i = 0; i < n; i++)
sum += x[i] * p[i];
Console.WriteLine(sum);
Console.Read();
}
}
}