动态规划——背包问题升级

文章出处：极客时间《数据结构和算法之美》-作者：王争。该系列文章是本人的学习笔记。

背包能够承受的总重量一定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;}

总结

以上是生活随笔为你收集整理的动态规划——背包问题升级的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。