题目描述

你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为$v_{i}v\_i$ ​ ,价值为$w_{i}w\_i$ ​ 。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

数据范围：$1\le v,v_i,w_i\le 1000\text{1}\le v,v_i\mathrm{},w_i\mathrm{}\le 10001\; \backslash le\; v,v\_i,w\_i\; \backslash le\; 1000\; \backslash 1\le v,v\_\; i\; \; ,w\_\; i\; \; \le 1000$

解题思路

· 本题是01背包问题的变种，解题思路也与01背包相似。代码如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param v int整型 
     * @param n int整型 
     * @param nums int整型ArrayList<ArrayList<>> 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> knapsack (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //问题1
        int[] dp = new int[v+1];
        //问题2
        int[] dp1 = new int[v+1];
        for(int i = 1;i <= v;++i){
            int max = Integer.MIN_VALUE;
            int max1 = Integer.MIN_VALUE;
            for(int j = 0;j < n;++j){
                if(i >= nums.get(j).get(0)){
                    // 遍历所有物品，找出能够装入当前背包的最大价值
                    max = Math.max(dp[i - nums.get(j).get(0)] + nums.get(j).get(1),max);
                    // 问题2要求背包正好装满，故无需去计算不装满背包的情况
                    max1 = Math.max(dp1[i - nums.get(j).get(0)] + nums.get(j).get(1),max1);
                }
                // 背包不装满
                max = Math.max(max,dp[i-1]);
            }
            dp[i] = max;
            dp1[i] = max1;
        }
        res.add(dp[v]);
        res.add(dp1[v] < 0 ? 0 : dp1[v]);
        return res;
    }
}