完全背包问题

和01背包问题的不同就是：完全背包问题可以在一个物品中选取多次
将其分解为：第i个物品选0个、1个…k-1个、k个
假设选择了k个:

1. 去掉k个物品i
2. 求max：f[i-1][j-K*v[i]]
3. 再加回来k个物品i

那么状态转移方程为：
dp[i][j] = dp[i - 1][j - k * v[i]] + k * w[i]

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int tolV = scan.nextInt();
        int[] v = new int[n+10];
        int[] w = new int[n+10];
        for(int i=1; i<=n; i++){
            v[i] = scan.nextInt();
            w[i] = scan.nextInt();
        }
        int[][] dp = new int[n+10][1010];

        for(int i=1; i<=n; i++){
            for(int j=0; j<=tolV; j++){
                for(int k=0; k * v[i] <= j; k++){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j - k*v[i]] + k * w[i]);
                }
            }
        }

        System.out.println(dp[n][tolV]);
    }
}

优化
根据原状态转移方程：f[i][j] = f[i-1][j-k*v[i]] + k*w[i]可推出
f[i][j] = Max(f[i-1][j], f[i-1][j-v] + w, f[i-1][j-2v] + 2w, f[i-1][j-3v] + 3w ......)
f[i][j-v] = Max( f[i-1][j-v], f[i-1][j-2v] + w, f[i-1][j-3v] + 2w ......)
所以可优化为：f[i][j] = Max(f[i-1][j], f[i][j-v] + w)

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int tolV = scan.nextInt();
        int[] v = new int[n+10];
        int[] w = new int[n+10];
        for(int i=1; i<=n; i++){
            v[i] = scan.nextInt();
            w[i] = scan.nextInt();
        }
        int[][] dp = new int[n+10][1010];

        for(int i=1; i<=n; i++){
            for(int j=0; j<=tolV; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= v[i]){
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);   
                }
            }
        }

        System.out.println(dp[n][tolV]);
    }
}