using?System;
using?System.Collections.Generic;
using?System.Linq;
using?System.Text;


namespace?WindowsFormsApplication1
{
????class?BagProblem
????{
???????public?int[]?profit;//物品價值
???????public?int[]?weight;//物品重量
???????public?int?numbers;//物品個數
???????public?int?capacity;//背包載重
???????public?int[]?d;?//最優決策數組

????????///?

????????///?向前回溯，確定所選的物品，記錄在x[]數組中
???????///?最優決策數組
???????///?用0、1記錄物體選取情況
????????///?

???????public?void?HuiSu（int[]?D?int[]?Weight?int?Capacity?int[]?x）
????????{
????????????numbers?=?Weight.Length?-?1;
????????????for?（int?i?=?0;?i?????????????????if?（d[i?Capacity]?==?1）
????????????????{
????????????????????x[i]?=?1;
????????????????????Capacity?-=?Weight[i];
????????????????}
????????????????else
????????????????????x[i]?=?0;
????????????x[numbers]?=?d[numbers?Capacity];
????????}
?????????
????????///?

????????///?求最大價值
????????///?物體價值
????????///?物體重量
????????///?背包載重
????????///?

????????public??int?MaxProfit（int[]?Profit?int[]?Weight?int?Capacity）
????????{
????????????profit?=?Profit;
????????????weight?=?Weight;
????????????numbers?=?Profit.Length?-?1;
????????????return?f（0?Capacity）;
????????
????????}

????????///?

????????///?根據遞推關系求解
????????///?

????????private?int?f（int?i?int?j）
????????{
????????????if?（i?==?numbers）//如果只有一個物品
????????????{
????????????????if?（j?????????????????{
????????????????????d[numbersj]?=?0;
????????????????????return?0;
????????????????}
????????????????else
????????????????{
????????????????????d[numbersj]?=?1;
????????????????????return?profit[numbers];
????????????????}
????????????}
????????????if?（j?????????????{
????????????????d[ij]?=?0;
????????????????return?f（i?+?1?j）;
????????????}
????????????////根據狀態轉移方程
????????????////f[ij]=max{f[i-1j]f[i-1j-w[i]]+p[i]}
????????????int?p0?=?f（i?+?1?j）;
????????????int?p1?=?f（i?+?1?j?-?weight[i]）?+?profit[i];
????????????if?（p0?????????????{
????????????????d[ij]?=?1;
????????????????return?p1;
????????????}
????????????else
????????????{
????????????????d[ij]?=?0;
????????????????return?p0;
????????????}
????????}
????}
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????2665??2009-12-03?16:39??WindowsFormsApplication1\WindowsFormsApplication1\BagProblem.cs

?????文件?????112640??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\bin\Debug\WindowsFormsApplication1.exe

?????文件??????30208??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\bin\Debug\WindowsFormsApplication1.pdb

?????文件??????14328??2009-12-03?16:44??WindowsFormsApplication1\WindowsFormsApplication1\bin\Debug\WindowsFormsApplication1.vshost.exe

?????文件????????490??2009-06-11?05:14??WindowsFormsApplication1\WindowsFormsApplication1\bin\Debug\WindowsFormsApplication1.vshost.exe.manifest

?????文件???????2865??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\Form1.cs

?????文件???????9112??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\Form1.Designer.cs

?????文件?????155634??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\Form1.resx

?????文件???????1259??2009-12-03?16:44??WindowsFormsApplication1\WindowsFormsApplication1\obj\Debug\WindowsFormsApplication1.csproj.FileListAbsolute.txt

?????文件????????847??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\obj\Debug\WindowsFormsApplication1.csproj.GenerateResource.Cache

?????文件?????112640??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\obj\Debug\WindowsFormsApplication1.exe

?????文件?????100244??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\obj\Debug\WindowsFormsApplication1.Form1.resources

?????文件??????30208??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\obj\Debug\WindowsFormsApplication1.pdb

?????文件????????180??2009-12-03?09:41??WindowsFormsApplication1\WindowsFormsApplication1\obj\Debug\WindowsFormsApplication1.Properties.Resources.resources

?????文件????????505??2009-12-02?10:22??WindowsFormsApplication1\WindowsFormsApplication1\Program.cs

?????文件???????1420??2009-12-03?16:39??WindowsFormsApplication1\WindowsFormsApplication1\Properties\AssemblyInfo.cs

?????文件???????2898??2009-12-02?10:22??WindowsFormsApplication1\WindowsFormsApplication1\Properties\Resources.Designer.cs

?????文件???????5612??2009-12-02?10:22??WindowsFormsApplication1\WindowsFormsApplication1\Properties\Resources.resx

?????文件???????1109??2009-12-02?10:22??WindowsFormsApplication1\WindowsFormsApplication1\Properties\Settings.Designer.cs

?????文件????????249??2009-12-02?10:22??WindowsFormsApplication1\WindowsFormsApplication1\Properties\Settings.settings

?????文件???????3835??2009-12-02?16:47??WindowsFormsApplication1\WindowsFormsApplication1\WindowsFormsApplication1.csproj

?????文件????????962??2009-12-02?10:22??WindowsFormsApplication1\WindowsFormsApplication1.sln

????..A..H.?????24064??2009-12-03?20:15??WindowsFormsApplication1\WindowsFormsApplication1.suo

?????目錄??????????0??2009-12-02?10:49??WindowsFormsApplication1\WindowsFormsApplication1\obj\Debug\Refactor

?????目錄??????????0??2009-12-02?10:22??WindowsFormsApplication1\WindowsFormsApplication1\obj\Debug\TempPE

?????目錄??????????0??2009-12-03?09:41??WindowsFormsApplication1\WindowsFormsApplication1\bin\Debug

?????目錄??????????0??2009-12-03?16:40??WindowsFormsApplication1\WindowsFormsApplication1\obj\Debug

?????目錄??????????0??2009-12-02?16:39??WindowsFormsApplication1\WindowsFormsApplication1\bin

?????目錄??????????0??2009-12-02?10:22??WindowsFormsApplication1\WindowsFormsApplication1\obj

?????目錄??????????0??2009-12-03?16:39??WindowsFormsApplication1\WindowsFormsApplication1\Properties

............此處省略5個文件信息