题解 | #完全背包#
完全背包
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;
}
}
