C#,背包问题Knaphotoshopack 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
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhhaffge
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13