文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

背包能夠承受的總重量一定w，每個物品的總量不同int[] weight表示，每個物品的價值不同用int[] values表示。怎么放才能讓背包中物品不超過最大重量，而且價值最大。

這道題目在0-1背包問題上升級了，多了一個價值這個維度。我們就在上一版本基礎上調整。state存放當前狀態下的最大價值。

public int knapsnackV3(int[] weight,int[] value, int n,int w){int[][] state = new int[n][w+1];int maxValue = -1;for(int i=0;i<n;i++){Arrays.fill(state[i],-1);}state[0][0] = 0;if(weight[0]<w){state[0][weight[0]] = value[0];}for(int i=1;i<n;i++){//不放入第i物品for(int j=0;j<=w;j++){if(state[i-1][j]>-1){state[i][j] = state[i-1][j];}}//放入第i物品for(int j=0;j<=w-weight[i];j++){if(state[i-1][j]>-1){int v = state[i-1][j]+value[i];if(v>state[i][j+weight[i]]){state[i][j+weight[i]] = v;}}}}for(int j=w;j>=0;j--){if(state[n-1][j]>-1){maxValue = Math.max(maxValue,state[n-1][j]);}}return maxValue;}

總結

以上是生活随笔為你收集整理的动态规划——背包问题升级的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。