51 lines
1.7 KiB
C#
51 lines
1.7 KiB
C#
using System; // 4790@3.6
|
|
using System.Threading.Tasks;
|
|
class Program
|
|
{
|
|
static void Main()
|
|
{
|
|
var sw = System.Diagnostics.Stopwatch.StartNew();
|
|
Console.Write(knapSack(400) + "\n" + sw.Elapsed); // 60 ms
|
|
Console.Read();
|
|
}
|
|
|
|
static string knapSack(uint w1)
|
|
{
|
|
uint sol = 0, v1 = 0;
|
|
Parallel.For(1, 9, t =>
|
|
{
|
|
uint j, wi, k, vi, i1 = 1u << w.Length;
|
|
for (uint i = (uint)t; i < i1; i += 8)
|
|
{
|
|
k = wi = vi = 0;
|
|
for (j = i; j > 0; j >>= 1, k++)
|
|
if ((j & 1) > 0)
|
|
{
|
|
if ((wi += w[k]) > w1) break;
|
|
vi += v[k];
|
|
}
|
|
if (wi <= w1 && v1 < vi)
|
|
lock (locker)
|
|
if (v1 < vi) { v1 = vi; sol = i; }
|
|
}
|
|
});
|
|
string str = "";
|
|
for (uint k = 0; sol > 0; sol >>= 1, k++)
|
|
if ((sol & 1) > 0) str += items[k] + "\n";
|
|
return str;
|
|
}
|
|
|
|
static readonly object locker = new object();
|
|
|
|
static byte[] w = { 9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11,
|
|
32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30 },
|
|
|
|
v = { 150, 35, 200, 160, 60, 45, 60, 40, 30, 10, 70,
|
|
30, 15, 10, 40, 70, 75, 80, 20, 12, 50, 10 };
|
|
|
|
static string[] items = {"map","compass","water","sandwich","glucose","tin",
|
|
"banana","apple","cheese","beer","suntan cream",
|
|
"camera","T-shirt","trousers","umbrella",
|
|
"waterproof trousers","waterproof overclothes",
|
|
"note-case","sunglasses","towel","socks","book"};
|
|
}
|