C語言數(shù)學問題與簡單DP01背包問題詳解

第C語言數(shù)學問題與簡單DP01背包問題詳解}

這中間有一個點大家可能不太好理解，為什么是for(intj=m;j=v[i];j--)，而不是for(intj=v[i];jj++)

首先我們先來模擬一下如果是for(intj=v[i];jj++)，循環(huán)就是：

for(inti=1;ii++){

for(intj=v[i];jj++){

f[j]=max(f[j],f[j-v[i]]+w[i]);

來看題

輸入樣例

45

12

24

34

45

物品體積價值

i=112

i=224

i=334

i=445

當還沒進循環(huán)的時候

f[0]=0;f[1]=0;f[2]=0;f[3]=0;f[4]=0;f[5]=0;

當進入循環(huán)i==1時：v[i]=1,w[i]=2;

j=1:f[1]=max(f[1],f[1-1]+2),即max(0,2)=2;即f[1]=2;

j=2:f[2]=max(f[2],f[2-1]+2),即max(0,4)=4;即f[2]=4;

j=3:f[3]=max(f[3],f[3-1]+2),即max(0,6)=6;即f[3]=6;

j=4:f[4]=max(f[4],f[4-1]+2),即max(0,8)=8;即f[4]=8;

j=5:f[5]=max(f[5],f[5-1]+2),即max(0,10)=10;即f[5]=10;

當?shù)竭@里的時候就已經(jīng)出問題了。

//如果j層循環(huán)是逆序的：for(inti=1;ii++){!--{C}%3C!%2D%2D%20%2D%2D%3E--for(intj=m;j=v[i];j--){!--{C}%3C!%2D%2D%20%2D%2D%3E--f[j]=max(f[j],f[j-v[i]]+w[i]);}}//如果j層循環(huán)是逆序的：

for(inti=1;ii++){

for(intj=m;j=v[i];j--){

f[j]=max(f[j],f[j-v[i]]+w[i]);

輸入樣例

45

12

24

34

45

物品體積價值

i=112

i=224

i=334

i=445

當還沒進循環(huán)的時候

f[0]=0;f[1]=0;f[2]=0;f[3]=0;f[4]=0;f[5]=0;

當進入循環(huán)時i==1，w[i]=2,v[i]=1;

j=5:f[5]=max(f[5],f[5-1]+2),即max(0,2)=2;即f[5]=2;

j=4:f[4]=max(f[4],f[4-1]+2),即max(0,2)=2;即f[4]=2;

j=3:f[3]=max(f[3],f[3-1]+2),即max(0,2)=2;即f[3]=2;

j=2:f[2]=max(f[2],f[2-1]+2),即max(0,2)=2;即f[2]=2;

j=1:f[1]=max(f[1],f[1-1]+2),即max(0,2)=2;即f[1]=2;

當進入循環(huán)i==2時,w[i]=4,v[i]=2;

j=5:f[5]=max(f[5],f[5-2]+4),即max(2,6)=6,即f[5]=6;

j=4:f[5]=max(f[4],f[4-2]+4),即max(2,6)=6,即f[4]=6;

j=3:f[5]=max(f[3],f[3-2]+4),即max(2,6)=6,即f[3]=6;

j=2:f[5]=max(f[2],f[2-2]+4),即max(2,4)=4,即f[2]=4;

當進入循環(huán)i==3時:w[i]=4;v[i]=3;

j=5:f[5]=max(f[5],f[5-3]+4),即max(6,8)=8,即f[5]=8;

j=4:f[4]=max(f[4],f[4-3]+4),即max(6,6)=6,即f[4]=6;

j=3:f[3]=max(f[3],f[3-3]+4),即max(6,4)=6,即f[3]=6;

當進入循環(huán)i==3時:w[i]=5;v[i]=4;

j=5:f[5]=max(f[5],f[5-4]+5),即max(8,7)=8,即f[5]=8;

j=4:f[4]=max(f[4],f[4-4]+5),即max(6,5)=6,即f[4]=6;

模擬結(jié)束，最后max=8：發(fā)現(xiàn)沒有錯誤，即逆序就可以解決這個優(yōu)化的問題了

最后為什么一維情況下枚舉背包容量需要逆序？

在二維情況下，狀態(tài)f[i][j]是由上一輪i-1的狀態(tài)得來的，f[i][j]與f[i-1][j]是獨