背包承重为10，价值是V的物品，重量为W，求解装的最大价值
C=10
i V W
1 10 2 最优解：60
2 20 4
3 30 6
4 40 5
10到0的最大价值初始都为0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
0 0 0 0 0 0 0 0 0 0 0
for (i = 1; i <= 4; i++)
{
for (int c = 10; c >= c[i]; c--)
{
if(f[c - weightArray[i]] + valueArray[i] >= f[c])
{
f[c]=f[c - weightArray[i]] + valueArray[i];
}
}
}
f[c - weightArray[i]] + valueArray[i] f[c]
i=1 weightArray[i]=2 valueArray[i]=10
c=10 f[8] + 10 = 10 >= f[10] = 0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
10 0 0 0 0 0 0 0 0 0 0
c=9 f[7] + 10 = 10 >= f[9] = 0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
10 10 0 0 0 0 0 0 0 0 0
c=8 f[6] + 10 = 10 >= f[8] = 0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
10 10 10 0 0 0 0 0 0 0 0
c=7 f[5] + 10 = 10 >= f[7] = 0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
10 10 10 10 0 0 0 0 0 0 0
c=6 f[4] + 10 = 10 >= f[6] = 0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
10 10 10 10 10 0 0 0 0 0 0
c=5 f[3] + 10 = 10 >= f[5] = 0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
10 10 10 10 10 10 0 0 0 0 0
c=4 f[2] + 10 = 10 >= f[4] = 0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
10 10 10 10 10 10 10 0 0 0 0
c=3 f[1] + 10 = 10 >= f[3] = 0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
10 10 10 10 10 10 10 10 0 0 0
c=2 f[0] + 10 = 10 >= f[2] = 0
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
10 10 10 10 10 10 10 10 10 0 0
i=2 weightArray[i]=4 valueArray[i]=20
c=10 f[6] + 20 = 30 >= f[10] = 10
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
30 10 10 10 10 10 10 10 10 0 0
c=9 f[5] + 20 = 30 >= f[9] = 10
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
30 30 10 10 10 10 10 10 10 0 0
c=8 f[4] + 20 = 30 >= f[8] = 10
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
30 30 30 10 10 10 10 10 10 0 0
c=7 f[3] + 20 = 30 >= f[7] = 10
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
30 30 30 30 10 10 10 10 10 0 0
c=6 f[2] + 20 = 30 >= f[6] = 10
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
30 30 30 30 30 10 10 10 10 0 0
c=5 f[1] + 20 = 20 >= f[5] = 10
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
30 30 30 30 30 20 10 10 10 0 0
c=4 f[0] + 20 = 20 >= f[4] = 10
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
30 30 30 30 30 20 20 10 10 0 0
i=3 weightArray[i]=6 valueArray[i]=30
c=10 f[4] + 30 = 50 >= f[10] = 30
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
50 30 30 30 30 20 20 10 10 0 0
c=9 f[3] + 30 = 40 >= f[9] = 30
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
50 40 30 30 30 20 20 10 10 0 0
c=8 f[2] + 30 = 40 >= f[8] = 30
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
50 40 40 30 30 20 20 10 10 0 0
c=7 f[1] + 30 = 30 >= f[7] = 30
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
50 40 40 30 30 20 20 10 10 0 0
c=6 f[0] + 30 = 30 >= f[6] = 30
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
50 40 40 30 30 20 20 10 10 0 0
i=4 weightArray[i]=5 valueArray[i]=40
c=10 f[5] + 40 = 60 >= f[10] = 50
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
60 40 40 30 30 20 20 10 10 0 0
c=9 f[4] + 40 = 60 >= f[9] = 40
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
60 60 40 30 30 20 20 10 10 0 0
c=8 f[3] + 40 = 50 >= f[8] = 40
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
60 60 50 30 30 20 20 10 10 0 0
c=7 f[2] + 40 = 50 >= f[7] = 30
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
60 60 50 50 30 20 20 10 10 0 0
c=6 f[1] + 40 = 40 >= f[6] = 30
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
60 60 50 50 40 20 20 10 10 0 0
c=5 f[0] + 40 = 40 >= f[5] = 20
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
60 60 50 50 40 40 20 10 10 0 0
C=10
i V W
1 10 2 最优解：60
2 20 4
3 30 6
4 40 5
f[10] f[9] f[8] f[7] f[6] f[5] f[4] f[3] f[2] f[1] f[0]
60 60 50 50 40 40 20 10 10 0 0
承重10的最大价值60
求解思路理解： 把所有的承重的最大值算出来
