算法-动态规划-完全背包

Keep thinking. / 2024-08-29 / 原文

0. 动态规划五部曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

1. 完全背包问题

完全背包问题中，每个物品都有无数个，可以重复选择。

二维dp数组

    int[][] dp = new int[n][totalWeight+1];
    
    // 初始化第一行
    for(int j = weight[0]; j<=totalWeight; ++j) {
        dp[0][j] = value[0] * (j/weight[0]);
    }
    
    for(int i = 1; i<n; ++i) {
        for(int j = 0; j<=totalWeight; ++j) {
            if(j < weight[i])
                dp[i][j] = dp[i-1][j];
            else 
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-weight[i]]+value[i]);
        }
    }

一维dp数组：顺序遍历，允许同种物品被重复选择。

    int[] dp = new int[totalWeight+1];
    for(int i = 0; i<n; ++i) {
        for(int j = weight[i]; j<=totalWeight; ++j) {
            dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
        }
    }

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int totalWeight = scanner.nextInt();
        int[] weight = new int[n];
        int[] value = new int[n];
        
        for(int i = 0; i<n; ++i) {
            weight[i] = scanner.nextInt();
            value[i] = scanner.nextInt();
        }
        
        int[] dp = new int[totalWeight+1];
        for(int i = 0; i<n; ++i) {
            // 顺序遍历，同一个物品可以重复选
            for(int j = weight[i]; j<=totalWeight; ++j) {
                dp[j] = Math.max(dp[j], dp[j-weight[i]]+value[i]);
            }
        }
        
        System.out.println(dp[totalWeight]);
    }
}