题意整理。

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

方法一（动态规划）

1.解题思路

第一问：

• 状态定义：dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品。
• 状态转移：遍历所有的物品，要么选择当前物品，要么不选，取价值最大的，并且通过这种方式跟新所有情况的状态。即$dp1[j]=Math\mathrm{.}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[j]=Math\mathrm{.}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[i];j<=V;j++){
                //状态转移，要么选择当前物品，要么不选，取较大的
                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时，价值初始化为0
        dp2[0]=0;
        for(int i=1;i<=n;i++){
            for(int j=v[i];j<=V;j++){
                //状态转移，要么选择当前物品，要么不选，取较大的
                dp2[j]=Math.max(dp2[j-v[i]]+w[i],dp2[j]);
            }
        }
        //如果小于0，说明不能由初始化为0的状态转移过来，无解
        if(dp2[V]<0){
            dp2[V]=0;
        }
        System.out.println(dp2[V]);
    }
}

3.复杂度分析

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