目录
完全背包理论基础
题目
题目描述：
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。
小明的行李箱所能承担的总重量为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。
输入描述：
第一行包含两个整数，N，V，分别表示研究材料的种类和行李空间
接下来包含 N 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值
输出描述：
输出一个整数，表示最大价值。
输入示例：
4 5
1 2
2 4
3 4
4 5
输出示例：
10
提示信息：
第一种材料选择五次，可以达到最大值。
数据范围：
1 <= N <= 10000;
1 <= V <= 10000;
1 <= wi, vi <= 10^9.
思路
视频讲解：带你学透完全背包问题！ 和 01背包有什么差别？遍历顺序上有什么讲究？
与01背包的区别是从小到大遍历背包容量。
在完全背包中，对于一维dp数组，遍历物品和背包容量的两个循环可以颠倒顺序，而01背包中的一维数组的遍历顺序一定是先遍历物品，再遍历背包容量。
题解
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int V = scanner.nextInt();
int[] weights = new int[N];
int[] values = new int[N];
for (int i = 0; i < N; i++) {
weights[i] = scanner.nextInt();
values[i] = scanner.nextInt();
}
scanner.close();
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
for (int j = weights[i]; j <= V; j++) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
System.out.println(dp[V]);
}
}
518.零钱兑换II
题目
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
提示：
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的所有值 互不相同0 <= amount <= 5000
思路
可以转换为完全背包问题。
- 确定dp数组以及下标的含义：
dp[j]为凑成金额 j 的方法数。 - 确定递推公式：
dp[j] += dp[j - coins[i]] - 初始化数组：
dp[0] = 1，组成金额 0 的方法有一种：什么金额都不选择。 - 确定遍历顺序：外层 for 循环遍历物品（钱币），内层 for 遍历背包（金钱总额），此时求得的是组合数，若顺序交换则求得排列数。
- 举例推导：
题解
class Solution {
public int change(int amount, int[] coins) {
int dp[] = new int[amount + 1];
dp[0] = 1;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
377. 组合总和 Ⅳ
题目
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
提示：
1 <= nums.length <= 2001 <= nums[i] <= 1000nums中的所有元素 互不相同1 <= target <= 1000
思路
可以转换为完全背包问题，注意题目要求求的为排列数。
- 确定dp数组以及下标的含义：
dp[i]为凑成目标正整数 i 的排列个数。 - 确定递推公式：
dp[i] += dp[i - nums[j]] - 初始化数组：
dp[0] = 1 - 确定遍历顺序： 求排列时外层遍历背包容量，内层遍历物品，同时完全背包问题使用顺序遍历。
- 举例推导：
题解
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i <= target; i++) {
for (int j = 0; j < nums.length; j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}
卡玛网 57. 爬楼梯（进阶版）
题目
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入描述：
输入共一行，包含两个正整数，分别表示n, m
输出描述：
输出一个整数，表示爬到楼顶的方法数。
输入示例：
3 2
输出示例：
3
提示信息：
数据范围：
1 <= m < n <= 32;
当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶段
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
思路
- 确定dp数组以及下标的含义：
dp[i]为爬到第 i 个台阶的方法数 - 确定递推公式：
dp[i] += dp[i - j] - 初始化数组：
dp[0] = 1 - 确定遍历顺序： 求排列时外层遍历背包容量，内层遍历物品，同时完全背包问题使用顺序遍历。
- 举例推导：同上题
题解
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
scanner.close();
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i - j >= 0) {
dp[i] += dp[i - j];
}
}
}
System.out.println(dp[n]);
}
}