题意整理。

• 给定一个背包，能容纳体积为V。然后有n种物品，每种物品有一个对应的体积和价值。每种物品只提供一个。
• 求这个背包最多能装多大价值的物品。
• 如果背包恰好装满，最多能装多大价值的物品。

方法一（动态规划）

1.解题思路

第一问：

• 状态定义：dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品。
• 状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即$dp1\left[j\right]=Math.max\left(dp1\right[j-v\left[i\right]]+w[i],dp1[j\left]\right)dp1[j]=Math.max(dp1[j-v[i]]+w[i],dp1[j])$dp1[j]=Math.max(dp1[j−v[i]]+w[i],dp1[j])。

第二问：

• 状态定义：dp2[i]表示背包恰好装满时，在容量为i的情况下，最多装多大价值的物品。
• 状态初始化：将背包容量为0的情况设置价值为0，其它情况设置为最小的Integer型整数，表示不可达状态。后续所有的状态都需要从为0的状态转移过去。
• 状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即$dp2\left[j\right]=Math.max\left(dp2\right[j-v\left[i\right]]+w[i],dp2[j\left]\right)dp2[j]=Math.max(dp2[j-v[i]]+w[i],dp2[j])$dp2[j]=Math.max(dp2[j−v[i]]+w[i],dp2[j])。

图解展示：

第一问：

第二问：

2.代码实现

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int V = sc.nextInt();
        //存放体积
        int[] v=new int[n+1];
        //存放价值
        int[] w=new int[n+1];
        for(int i=1;i<=n;i++){
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
        }
        
        //dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品
        int[] dp1=new int[V+1];
        for(int i=1;i<=n;i++){
            //由于每个物品只能用一次，为了防止重复计算，需要倒序遍历
            for(int j=V;j>=v[i];j--){
                //状态转移，要么选择第i件物品，要么不选，取价值最大的
                dp1[j]=Math.max(dp1[j-v[i]]+w[i],dp1[j]);
            }
        }
        
        System.out.println(dp1[V]);
        
        //dp2[i]表示背包恰好装满时，在容量为i的情况下，最多装多大价值的物品
        int[] dp2=new int[V+1];
        Arrays.fill(dp2,Integer.MIN_VALUE);
        //没有物品时，价值为0
        dp2[0]=0;
        for(int i=1;i<=n;i++){
            //由于每个物品只能用一次，为了防止重复计算，需要倒序遍历
            for(int j=V;j>=v[i];j--){
                //状态转移，要么选择第i件物品，要么不选，取价值最大的
                dp2[j]=Math.max(dp2[j-v[i]]+w[i],dp2[j]);
            }
        }
        //如果小于0，说明不能从初始状态转移过来，无解
        if(dp2[V]<0){
            dp2[V]=0;
        }
        System.out.println(dp2[V]);
    }
}

3.复杂度分析

• 时间复杂度：两层循环，最多需要遍历$n\ast Vn*V$n∗V次，所以时间复杂度为$O(n\ast V)O(n*V)$O(n∗V)。
• 空间复杂度：需要额外大小为$V+1V+1$V+1的dp1数组和dp2数组，所以空间复杂度为$O\left(V\right)O(V)$O(V)。