C#使用动态规划解决0-1背包问题实例分析
本文实例讲述了C#使用动态规划解决0-1背包问题的方法。分享给大家供大家参考。具体如下：
//利用动态规划解决0-1背包问题
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
namespaceKnapsack_problem
//背包问题关键在于计算不超过背包的总容量的最大价值
{
classProgram
{
staticvoidMain()
{
inti;
intcapacity=16;
int[]size=newint[]{3,4,7,8,9};
//5件物品每件大小分别为3,4,7,8,9
//且是不可分割的0-1背包问题
int[]values=newint[]{4,5,10,11,13};
//5件物品每件的价值分别为4,5,10,11,13
int[]totval=newint[capacity+1];
//数组totval用来存贮最大的总价值
int[]best=newint[capacity+1];
//best存贮的是当前价值最高的物品
intn=values.Length;
for(intj=0;j<=n-1;j++)
for(i=0;i<=capacity;i++)
if(i>=size[j])
if(totval[i]<(totval[i-size[j]]+values[j]))
//如果当前的容量减去J的容量再加上J的价值比原来的价值大，
//就将这个值传给当前的值
{
totval[i]=totval[i-size[j]]+values[j];
best[i]=j;//并把j传给best
}
Console.WriteLine("背包的最大价值:"+totval[capacity]);
//Console.WriteLine("构成背包的最大价值的物品是:");
//inttotcap=0;
//while(totcap<=capacity)
//{
//Console.WriteLine("物品的大小是："+size[best[capacity-totcap]]);
//for(i=0;i<=n-1;i++)
//totcap+=size[best[i]];
//}
}
}
}
希望本文所述对大家的C#程序设计有所帮助。