amir.tak
عضو جدید
کد:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace dynamic_knapsack
{
class Program
{
/// Cite http://daneshju-club.com if you want to use the source code
///writing by navid
static int n, i, W, w;
static int[] weight;
static int[] v;
static int[,] C;
static void Main(string[] args)
{
weight = new int[50];
v = new int[50];
C = new int[50, 50];
Console.WriteLine("Enter number of items:");
n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Enter knapsack capacity:");
W = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Enter item weights:");
for (i = 0; i < n; i++)
{
Console.Write("Enter weight of item ( " + (i + 1) + " ): ");
weight[i] = Convert.ToInt32(Console.ReadLine()); ;
}
Console.WriteLine("Enter item values:");
for (i = 0; i < n; i++)
{
Console.Write("Enter value of item with weight ( " + weight[i] + " ): ");
v[i] = Convert.ToInt32(Console.ReadLine());
}
knapsack(n, W);
Console.ReadLine();
}
static void knapsack(int n, int W)
{
/*for(int c = 0; c <= W; c++){
C[0][c] = 0;
}*/
for (i = 1; i <= n; i++)
{
C[i, 0] = 0;
//cout<<C[i][0];
}
for (i = 1; i <= n; i++)
{
for (w = 0; w <= W; w++)
if (weight[i] <= w) //item can be put in knapsack
if (v[i] + C[i - 1, w - weight[i]] > C[i - 1, w])
C[i, w] = v[i] + C[i - 1, w - weight[i]];
else
C[i, w] = C[i - 1, w];
else
C[i, w] = C[i - 1, w]; // w[i]>w
}
Console.WriteLine();
Console.WriteLine("The upper value is :" + C[i - 1, w - 1]);
//return C[i-1][w-1];
}
}
}