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#程序设计有所帮助。