01背包问题 动态规划
01背包问题 动态规划
很有意思的问题。
写了点代码 C#实现
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Net.Mime.MediaTypeNames;
namespace Package
{
public class Item
{
public int weight;
public int value;
public Item(int w, int val)
{
weight = w;
value = val;
}
}
public class Problem
{
//背包容量
int content;
int item_cnt;
Item[] items;
int[,] dps;
public Problem()
{
}
public void Init()
{
Console.Write("请输入背包容量(正整数):");
string con = Console.ReadLine();
while (!int.TryParse(con, out content) || content < 0)
{
Console.Write("输入错误，请输入背包容量(正整数):");
con = Console.ReadLine();
}
Console.Write("请输入物品数量(正整数):");
con = Console.ReadLine();
while (!int.TryParse(con, out item_cnt) || item_cnt < 0)
{
Console.Write("输入错误，请输入物品数量(正整数):");
con = Console.ReadLine();
}
items = new Item[item_cnt];
int temp_weight = 0, temp_val = 0;
for (int idx = 0; idx < items.Length; idx++)
{
Console.Write("请输入物品{0}重量(正整数):", idx+1);
con = Console.ReadLine();
while (!int.TryParse(con, out temp_weight) || temp_weight < 0)
{
Console.Write("输入错误，请输入物品{0}重量(正整数):", idx + 1);
con = Console.ReadLine();
}
Console.Write("请输入物品{0}价值(正整数):", idx + 1);
con = Console.ReadLine();
while (!int.TryParse(con, out temp_val) || temp_val < 0)
{
Console.Write("输入错误，请输入物品{0}价值(正整数):", idx + 1);
con = Console.ReadLine();
}
items[idx] = new Item(temp_weight, temp_val);
}
}
public void Display()
{
Console.WriteLine("========问题信息========");
Console.WriteLine("背包容量:{0} 物品数量:{1}", content, item_cnt);
for (int idx = 0; idx < items.Length; idx++)
{
Console.WriteLine("物品{0} (重量:{1} 价值:{2})", idx+1, items[idx].weight, items[idx].value);
}
}
public void Cal()
{
int h_cnt = item_cnt + 1;
int l_cnt = content + 1;
dps = new int[h_cnt, l_cnt];
for (int item = 0;item < h_cnt; item++)
{
for (int cidx = 0; cidx < l_cnt; cidx++)
{
if (item == 0)
{
dps[item, cidx] = 0;
}
else
{
if (cidx < items[item - 1].weight)//背包在此容量下压根就装不上
{
dps[item, cidx] = dps[item - 1, cidx];
}
else//能装 装和不装取最大
{
dps[item, cidx] = Math.Max(dps[item-1, cidx], dps[item-1, cidx-items[item-1].weight] + items[item-1].value);
}
}
}
}
}
public void Answer()
{
Console.WriteLine("========dp table========");
for (int h = 1; h < item_cnt + 1; h++)
{
for (int l = 0; l < content + 1; l++)
{
Console.Write("{0} ", dps[h, l]);
}
Console.WriteLine();
}
Console.WriteLine("最大价值:{0}", dps[item_cnt, content]);
Console.Write("背包信息:");
Plan(item_cnt, content);
Console.WriteLine();
}
void Plan(int h, int l)
{
if (l <= 0 || h <= 0)
return;
if (dps[h - 1,l] != dps[h,l])
{
Plan(h-1, l - items[h-1].weight);
Console.Write("物品{0} ", h);
}
else
{
Plan(h-1, l);
}
}
}
internal class Program
{
static bool IsContinue()
{
Console.WriteLine("是否继续(Y/N)?");
string val = Console.ReadLine();
while (val != "Y" && val != "y" && val != "N" && val != "n")
{
Console.WriteLine("是否继续(Y/N)?");
val = Console.ReadLine();
}
if (val == "Y" || val == "y")
{
return true;
}
else
{
return false;
}
}
static void Main(string[] args)
{
Problem problem = new Problem();
do
{
problem.Init();
problem.Display();
problem.Cal();
problem.Answer();
} while (IsContinue());
}
}
}
程序运行结果
