回复 6 楼 巧若拙
你的注释很棒,否则根本看不懂版主大人的回复。我再加一个我自己的理解吧。
程序代码:
f[k][j] += f[k-a[i]][j-1]; //这里是最关键的,也是动态规划的核心,
下面是我调试理解这个程序的时候,打印出来的结果。我分析之后才明白,
比如 f[2][1]+=f[1][0]]=0 表示当子问题为金额2元时,用1张纸币如何获得最优解
因为之前已经包含了一张a[i]元的纸币,这里a[i]=1,所以这个子问题的最优解就是,去掉
a[i]元钱(1元钱)和去掉a[i]元钱的容量(即一张)的最优解。。
从小规模循环至答案。
4
f[1][1]+=f[1-a[0]][1-1]]=1
f[1][1]+=f[0][0]]=1
f[2][1]+=f[2-a[0]][1-1]]=0
f[2][1]+=f[1][0]]=0
f[2][2]+=f[2-a[0]][2-1]]=1
f[2][2]+=f[1][1]]=1
f[3][1]+=f[3-a[0]][1-1]]=0
f[3][1]+=f[2][0]]=0
f[3][2]+=f[3-a[0]][2-1]]=0
f[3][2]+=f[2][1]]=0
f[3][3]+=f[3-a[0]][3-1]]=1
f[3][3]+=f[2][2]]=1
f[4][1]+=f[4-a[0]][1-1]]=0
f[4][1]+=f[3][0]]=0
f[4][2]+=f[4-a[0]][2-1]]=0
f[4][2]+=f[3][1]]=0
f[4][3]+=f[4-a[0]][3-1]]=0
f[4][3]+=f[3][2]]=0
f[4][4]+=f[4-a[0]][4-1]]=1
f[4][4]+=f[3][3]]=1
f[2][1]+=f[2-a[1]][1-1]]=1
f[2][1]+=f[0][0]]=1
f[2][2]+=f[2-a[1]][2-1]]=1
f[2][2]+=f[0][1]]=1
f[3][1]+=f[3-a[1]][1-1]]=0
f[3][1]+=f[1][0]]=0
f[3][2]+=f[3-a[1]][2-1]]=1
f[3][2]+=f[1][1]]=1
f[3][3]+=f[3-a[1]][3-1]]=1
f[3][3]+=f[1][2]]=1
f[4][1]+=f[4-a[1]][1-1]]=0
f[4][1]+=f[2][0]]=0
f[4][2]+=f[4-a[1]][2-1]]=1
f[4][2]+=f[2][1]]=1
f[4][3]+=f[4-a[1]][3-1]]=1
f[4][3]+=f[2][2]]=1
f[4][4]+=f[4-a[1]][4-1]]=1
f[4][4]+=f[2][3]]=1
3