背包问题

背包能放入的最大重量：

物品 1 重量：		价值：		删除
物品 2 重量：		价值：		删除
物品 3 重量：		价值：		删除
物品 4 重量：		价值：		删除
物品 5 重量：		价值：		删除
增加物品

计算

结果：

解决思路及核心代码

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

namespace Niunan.Tool.Web.Models
{
    /// <summary>
    /// 背包问题解决
    /// </summary>
    public class BeiBaoSolution
    {
        double maxvalue; //装入背包物品的最大价值
        bool[] select1; //临时数组，select1[i]表示第i号物品是否在背包中，true在，false不在
        double limitweight;
        public string JieJue(List<OneGood> goods, double limitweight)
        {

            this.select1 = new bool[goods.Count];
            this.limitweight = limitweight;
            double totalprice = 0; //所有物品总价值
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < goods.Count; i++)
            {
                OneGood one = goods[i];
                sb.Append($"<div>物品{i + 1} 重量：{one.Weight}，价值：{one.Price} </div>");

                totalprice += one.Price;
                select1[i] = false; //初始各个物品都没有装入背包
            }
            sb.Append($"<div>背包最大能装的重量为：{limitweight}</div>");


            maxvalue = 0;//装入背包的物品的总价值
            BackPack(goods, 0, 0.0, totalprice);//调用函数将第1个物品装入背包

            double sumweight = 0;
            sb.Append($"<hr /><div>可以将以下物品装入背包，使背包的物品价值最大：</div>");
            for (int i = 0; i < goods.Count; i++)
            {
                OneGood one = goods[i];
                if (one.Selected)
                {
                    sb.Append($"<div>第 {i + 1} 号物品，重量：{one.Weight}，价值：{one.Price}</div>");
                    sumweight += one.Weight;
                }
            }
            sb.Append($"<div>总重量：{sumweight}，总价值：{maxvalue}</div>");
            return sb.ToString();
        }
        /// <summary>
        /// 递归解决问题
        /// </summary>
        /// <param name="goods">物品列表</param>
        /// <param name="i">需要试装入的物品序号</param>
        /// <param name="tw">当前背包已经达到的总重量</param>
        /// <param name="tv">所有未装入背包的物品的总价值</param> 
        private void BackPack(List<OneGood> goods, int i, double tw, double tv)
        {
            if (tw + goods[i].Weight <= limitweight)
            {
                //试装入物品i，未超重
                select1[i] = true; //设置当前物品已经加入背包
                if (i < goods.Count - 1)
                {
                    //物品不是最后一个物品，递归调用，继续试装入下一物品
                    BackPack(goods, i + 1, tw + goods[i].Weight, tv);
                }
                else
                {
                    //已经是最后一个物品了，将状态标志复制到select1数组中，保存当前背包中的最大价值
                    for (int k = 0; k < goods.Count; k++)
                    {
                        goods[k].Selected = select1[k];
                    }
                    maxvalue = tv;
                }
            }
            //装入物品i后，超重了，再从背包中取出物品i
            select1[i] = false;
            if (tv - goods[i].Price > maxvalue)
            {
                //若未装入背包的物品的总价值减去物品i的价值还大于maxvalue，说明还可以继续向背包中添加物品
                if (i < goods.Count - 1)
                {
                    //物品不是最后一个物品，递归调用，继续试装入下一物品
                    BackPack(goods, i + 1, tw, tv - goods[i].Price);
                }
                else
                {
                    //已经是最后一个物品了，将状态标志复制到select1数组中，保存当前背包中的最大价值
                    for (int k = 0; k < goods.Count; k++)
                    {
                        goods[k].Selected = select1[k];
                    }
                    maxvalue = tv - goods[i].Price;
                }
            }
        }
    }
    /// <summary>
    /// 背包里的一样物品
    /// </summary>
    public class OneGood
    {
        /// <summary>
        /// 价值
        /// </summary>
        public double Price { set; get; }
        /// <summary>
        /// 重量
        /// </summary>
        public double Weight { set; get; }
        /// <summary>
        /// 是否装入背包
        /// </summary>
        public bool Selected { set; get; } = false;

    }
}