C#，背包问题（Knapsack Problem）贪心算法的源代码

背包问题（KnapSack?Problem）的相关算法是常用的规划算法。

一、什么是背包问题？

背包的问题是，你有一个“袋子”，可以装有限数量的物品，鉴于你有一组物品可以从每个物品中选择，每个物品都有各自的“价值”，你如何才能最大限度地只装最有价值的物品呢。

让我们以现实世界为例。一个强盗闯入一家珠宝店，想偷珍贵的珠宝。他的背包只能装50公斤重（他是超人）。当他在商店里走来走去想偷什么的时候，他必须在脑子里做一个“成本/收益”的总和，以最大限度地提高他的总收入。举个例子，用一个50公斤的袋子，偷一件价值100美元的50公斤物品，还是偷五件价值50美元的10公斤物品更好？显然是后者，因为即使一件物品更有价值，它也会占据袋子里的所有空间，而偷多件较小的物品实际上会使袋子的价值最大化。这就是背包问题。

下载完整的工程文件源代码：

下载源代码https://download.csdn.net/download/beijinghorn/85078706

二、背包问题（Knapsack Problem）贪心算法的C#源代码

1、核心代码

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
? ? public class Jewel
? ? {
? ? ? ? public int Weight { get; set; }
? ? ? ? public int Value { get; set; }
? ? }

? ? public static class KnapSack_Algorithm
? ? {
? ? ? ? public static int MaxCapacity(int bagCapacity, int[] weights, int[] values)//
? ? ? ? {
? ? ? ? ? ? List<Jewel> jewels = new List<Jewel>();
? ? ? ? ? ? for (int i = 0; i < weights.Length; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Jewel jewel = new Jewel();
? ? ? ? ? ? ? ? jewel.Weight = weights[i];
? ? ? ? ? ? ? ? jewel.Value = values[i];
? ? ? ? ? ? ? ? jewels.Add(jewel);
? ? ? ? ? ? }

? ? ? ? ? ? int itemCount = jewels.Count;
? ? ? ? ? ? int[,] matrix = new int[itemCount + 1, bagCapacity + 1];

? ? ? ? ? ? for (int i = 0; i <= itemCount; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? for (int w = 0; w <= bagCapacity; w++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if (i == 0 || w == 0)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? matrix[i, w] = 0;
? ? ? ? ? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? var currentJewelIndex = i - 1;
? ? ? ? ? ? ? ? ? ? var currentJewel = jewels[currentJewelIndex];
? ? ? ? ? ? ? ? ? ? if (currentJewel.Weight <= w)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? matrix[i, w] = Math.Max(currentJewel.Value + matrix[i - 1, w - currentJewel.Weight], matrix[i - 1, w]);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? matrix[i, w] = matrix[i - 1, w];
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? return matrix[itemCount, bagCapacity];
? ? ? ? }
? ? }
}
?

2、显示代码

using System;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.ComponentModel;
using System.Windows.Forms;

using Legalsoft.Truffer.Algorithm;

namespace Knapsack
{
? ? public partial class Form1 : Form
? ? {
? ? ? ? public Form1()
? ? ? ? {
? ? ? ? ? ? this.StartPosition = FormStartPosition.CenterScreen;
? ? ? ? ? ? InitializeComponent();
? ? ? ? }

? ? ? ? private void Form1_Load(object sender, EventArgs e)
? ? ? ? {
? ? ? ? ? ? this.Text = "C#，背包问题的KnapSack算法——北京联高软件开发有限公司";
? ? ? ? ? ? label1.Text = "Weights:";
? ? ? ? ? ? label2.Text = "Values:";
? ? ? ? ? ? label3.Text = "bagCapacity:";
? ? ? ? ? ? button1.Text = "KnapSack";
? ? ? ? ? ? button1.Cursor = Cursors.Hand;
? ? ? ? ? ? panel1.Dock = DockStyle.Top;
? ? ? ? ? ? panel2.Dock = DockStyle.Fill;
? ? ? ? ? ? textBox1.Text = "50,80,110,230";
? ? ? ? ? ? textBox2.Text = "10,20,30,40";
? ? ? ? ? ? textBox3.Text = "260";
? ? ? ? }

? ? ? ? private int[] String2Array(string str)
? ? ? ? {
? ? ? ? ? ? string[] ws = str.Trim().Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries);
? ? ? ? ? ? int[] array = new int[ws.Length];
? ? ? ? ? ? for (int i = 0; i < ws.Length; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (Int32.TryParse("0" + ws[i], out int wv))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? array[i] = wv;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? return array;
? ? ? ? }

? ? ? ? private void button1_Click(object sender, EventArgs e)
? ? ? ? {
? ? ? ? ? ? if (Int32.TryParse(textBox3.Text, out int bagCapacity))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? string result = "MaxTotalValue=" + KnapSack_Algorithm.MaxCapacity(bagCapacity, String2Array(textBox1.Text), String2Array(textBox2.Text));
? ? ? ? ? ? ? ? webBrowser1.DocumentText = result;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
?

--------------------------------------------

POWER BY TRUFFER.CN