題意：存錢罐可以往里面放一些價值小的錢，但是時間久了就不知道里面有多少錢了，除非你打破它。現(xiàn)在給出空罐子的重量和最滿能裝到多重，然后給出每種硬幣的價值和重量，我們要在不打破它的情況下確認罐子里最少有多少錢。 for i 1~n; for j w[i]~weight； dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); 由于 http://blog.csdn.net/tbwood/article/details/22747215 這個大牛說過。當前狀態(tài)至于上一個狀態(tài)的當前位置和上一個狀態(tài)的前一個位置有關(guān)，可以用一維數(shù)組。 dp[i]=max(dp[j],dp[j-w[i]]+v[i]);