题解 | #完全背包#
完全背包
https://www.nowcoder.com/practice/3ed13831e2cc4613866edee237d5a804
动态规划,dp[i]表示体积为i时所能装的最大价值,转移方程:当体积i大于等于当前物品的体积时,考虑是否可以将该物品添加,进一步更新体积为i下所能获得的最大价值
- 考虑在体积为v的情况下(不装满),所能获得的最大价值,由于可以不装满,那么最大价值可以在体积为[1, v]内的最大值
- 考虑装满的情况,那么最大值就是dp[v],如何确定体积为v时一定可以装满?可以在给dp数组初始化时,设置dp[i]为Integer.MIN_VALUE, dp[0] = 0, 那么最后如果dp[v]的价值是一个负数,说明他的前面存在状态没有装一个商品,即从dp[i] = Integer.MIN_VALUE转移来的,那么直接使得dp[v] = 0表示无法装满
import java.util.*; public class Solution { public ArrayList<Integer> knapsack (int v, int n, ArrayList<ArrayList<Integer>> nums) { // write code here int len = nums.size(); int max = 0; // dp[i]表示体积为i时所能装的最大价值 int[] dp = new int[v+1]; Arrays.fill(dp, Integer.MIN_VALUE); dp[0] = 0; for(int i=1;i<=v;i++){ for(int j=0;j<n;j++){ List<Integer> list = nums.get(j); // 背包可以放下当前物品 if(i >= list.get(0)){ // 考虑是否可以更新为更大的价值 if(dp[i-list.get(0)] + list.get(1) > dp[i]){ dp[i] = Math.max(dp[i-list.get(0)] + list.get(1), dp[i]); } } } max = Math.max(max, dp[i]); } ArrayList<Integer> res = new ArrayList<>(); res.add(max); int val = dp[v]<0?0:dp[v]; res.add(val); return res; } }