背包问题相关算法题
0/1
P1048 采药
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
输入格式
第一行有 2 个整数 T和 M，用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的 M行每行包括两个在 1到 100之间（包括 11和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
求规定时间内采到药物的最大总价值。
>输入： >70 3 >71 100 >69 1 >1 2 >输出： >3
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[m];
int[] b = new int[m];
for (int i = 0; i < m; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
}
System.out.println(max(T, a, b));
}
public static int max(int T, int[] a, int [] b) {
int[] dp = new int[T + 1];
for (int i = 0; i < a.length; i++) {
for (int j = T; j >= a[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - a[i]] + b[i]);
}
}
return dp[T];
}
}P1060 开心的金明
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过NN元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的NN元。于是，他把每件物品规定了一个重要度，分为55等：用整数1-51−5表示，第55等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过NN元（可以等于NN元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第jj件物品的价格为v[j]v[j]，重要度为w[j]w[j]，共选中了kk件物品，编号依次为j_1,j_2,…,j_kj1,j2,…,j**k，则所求的总和为：
v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+ …+v[j_k] \times w[j_k]v[j1]×w[j1]+v[j2]×w[j2]+…+v[j**k]×w[j**k]。
请你帮助金明设计一个满足要求的购物单。
输入格式
第一行，为2个正整数，用一个空格隔开：n,m（其中N(<30000)表示总钱数，m(<25)为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v p（其中v*表示该物品的价格v≤10000)，p表示该物品的重要度(1-5)
输出不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)
>输入 >1000 5 >800 2 >400 5 >300 5 >400 3 >200 2 >输出： >3900
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 总钱数
int m = sc.nextInt(); // 种类
int[] a = new int[m];
int[] b = new int[m];
for (int i = 0; i < m; i++) {
a[i] = sc.nextInt();
b[i] = prices[i] * sc.nextInt();
}
System.out.println(max(T, a, a));
}
public static int max(int T, int[] a, int [] a) {
int[] dp = new int[T + 1];
for (int i = 0; i < a.length; i++) {
for (int j = T; j >= a[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - a[i]] + b[i]);
}
}
return dp[T];
}
}P1049 装箱问题
有一个箱子容量为V正整数，0≤V≤20000），同时有n个物品（0<n≤30，每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式
1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积
输出格式
1个整数，表示箱子剩余空间。
>输入： >24 >6 >8 >3 >12 >7 >9 >7 >输出： >0
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 箱子容量
int m = sc.nextInt(); // m个物品
int[] a = new int[m];
for (int i = 0; i < m; i++) {
a[i] = sc.nextInt();
}
System.out.println(T - max(T, a, a));
}
public static int max(int T, int[] a, int [] a) {
int[] dp = new int[T + 1];
for (int i = 0; i < prices.length; i++) {
for (int j = T; j >= a[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - a[i]] + a[i]);
}
}
return dp[n];
}
}P1164 小A点菜
A身上有M元，去餐馆点菜。餐馆有N种，第i种卖ai元。每种菜只有一份。A想要点菜，正好吧身上钱花完，问一共有多少种点菜方法。
>输入格式 >第一行是两个数字，表示N和M。 >第二行起N个正数ai>输入 >4 4 >1 1 2 2 >输出 >3
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 种类
int T = sc.nextInt(); // 总钱
int[] a = new int[n + 1]; // 多算一种
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
System.out.println(max(T, a));
}
public static int max(int T, int[] a) {
int[] dp = new int[T + 1];
dp[0] = 1;
for (int i = 1; i < a.length; i++) {
for (int j = T; j >= a[i]; j--) {
dp[j] += dp[j - a[i]]; // 转移 求方案数 累加
}
}
return dp[T];
}
}P1510 精卫填海
东海未填平的区域还需要至少体积为v的木石才可以填平，而西山上的木石还剩下n块，每块的体积和把它衔到东海需要的体力分别为k和m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为c。
>输入格式 >输入文件的第一行是三个整数：v、n、c。 >从第二行到第n+1行分别为每块木石的体积和把它衔到东海需要的体力。>输入 >100 2 10 >50 5 >50 5 >输出 >0>输入 >10 2 1 >50 5 >10 2 >输出 >Impossible
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 还剩T体积填完
int n = sc.nextInt(); // n块石头
int c = sc.nextInt(); // 体力
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
}
int k = max(T, a, b, c);
if (k == -1)
System.out.println("Impossible");
else
System.out.println(k);
}
public static int max(int T, int[] a, int[] b, int c) {
int[] dp = new int[c + 1];
int ans = -1;
for (int i = 0; i < a.length; i++) {
for (int j = c; j >= b[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - b[i]] + a[i]);
if (dp[j] >= T) // 填完判断
ans = Math.max(ans, c - j);
}
}
return ans;
}
}找零钱的硬币数组合
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
>输入: amount = 5, coins = [1, 2, 5] >输出: 4 >解释: 有四种方式可以凑成总金额: >5=5 >5=2+2+1 >5=2+1+1+1 >5=1+1+1+1+1>输入: amount = 3, coins = [2] >输出: 0 >解释: 只用面额2的硬币不能凑成总金额3。>输入: amount = 10, coins = [10] >输出: 1
class Solution {
public int change(int amount, int[] coins) {
if (coins == null) return 0;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
}分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
>输入: [1, 5, 11, 5] >输出: true >解释: 数组可以分割成 [1, 5, 5] 和 [11].>输入: [1, 2, 3, 5] >输出: false >解释: 数组不能分割成两个元素和相等的子集
0/1背包
class Solution {
public boolean canPartition(int[] nums) {
int sum = computeArraySum(nums);
if (sum % 2 != 0) return false;
int w = sum / 2;
boolean[] dp = new boolean[w + 1];
dp[0] = true;
for (int num : nums) {
for (int i = w; i >= num; i--) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[w];
}
private int computeArraySum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
}完全背包
P1616 疯狂的采药
输入第一行有两个整数，分别代表总共能够用来采药的时间 t和代表山洞里的草药的数目 m。
第 2到第 (m + 1) 行，每行两个整数，第 (i + 1)行的整数 ai, bi 分别表示采摘第 i 种草药的时间和该草药的价值。
>输入 >70 3 >71 100 >69 1 >1 2 >输出 >140
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int n = sc.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
}
System.out.println(max(T, a, b));
}
public static int max(int T, int[] a, int[] b) {
int[] dp = new int[T + 1];
for (int i = 0; i < a.length; i++) {
for (int j = a[i]; j <= T; j++) {
dp[j] = Math.max(dp[j], dp[j - a[i]] + b[i]);
}
}
return dp[T];
}
}零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
>输入：coins = [1, 2, 5], amount = 11 >输出：3 >解释：11 = 5 + 5 + 1>输入：coins = [2], amount = 3 >输出：-1>输入：coins = [1], amount = 0 >输出：0>输入：coins = [1], amount = 1 >输出：1>输入：coins = [1], amount = 2 >输出：2
完全背包问题
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] dp = new int[amount + 1];
for (int coin : coins) {
for (int i = coin; i <= amount; i++) { //将逆序遍历改为正序遍历
// 三种情况
if (i == coin) {
dp[i] = 1;
} else if (dp[i] == 0 && dp[i - coin] != 0) {
dp[i] = dp[i - coin] + 1;
} else if (dp[i - coin] != 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == 0 ? -1 : dp[amount];
}
}单词拆分
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。>输入: s = "leetcode", wordDict = ["leet", "code"] >输出: true >解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。>输入: s = "applepenapple", wordDict = ["apple", "pen"] >输出: true >解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。 注意你可以重复使用字典中的单词。>输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] >输出: false
求解顺序的完全背包问题
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word: wordDict) {
// 对物品的迭代应该放在最里层
int len = word.length();
if (len <= i && word.equals(s.substring(i - len , i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
}多重背包
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
输出为：对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。
>输入： >1 >8 2 >2 100 4 >4 100 2 >输出： >400
有一个体积为V的背包，有m种物品，每种物品有体积和价值，且数量一定。求背包能装下的最大价值。
输入为第一行两个整数V和m。接下来m行，每行3个整数，表示第i种物品的数量、体积和价值。
输出为一个整数，表示背包能装下的最大价值。
>输入： >10 4 >2 3 2 >2 4 3 >1 2 2 >4 5 3 >输出： >8
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // money
int m = sc.nextInt(); // m种类
int[] prices = new int[m];
int[] weights = new int[m];
int[] nums = new int[m];
for (int i = 0; i < m; i++) {
prices[i] = sc.nextInt();
weights[i] = sc.nextInt();
nums[i] = sc.nextInt();
}
System.out.println(max(n, prices, weights, nums));
}
public static int max(int n, int[] prices, int[] weights, int[] nums) {
int[] dp = new int[n + 1];
for (int i = 0; i < prices.length; i++) {
for (int j = n; j >= prices[i]; j--) {
for (int k = 1; k <= nums[i] && k * prices[i] <= j; k++) {
dp[j] = Math.max(dp[j], dp[j - k * prices[i]] + k * weights[i]);
}
}
}
return dp[n];
}
}多维费用背包
P1507 NASA的食物计划
航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.
输入为：
第一行 两个数 体积最大值(<400)和质量最大值(<400)
第二行 一个数 食品总数N(<50).
第三行－第3+N行
每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)
输出为：
一个数 所能达到的最大卡路里(int范围内)
>输入： >320 350 >4 >160 40 120 >80 110 240 >220 70 310 >40 400 220 >输出： >550
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int vMax = sc.nextInt();
int mMax = sc.nextInt();
int m = sc.nextInt();
int[] vs = new int[m];
int[] ms = new int[m];
int[] kas = new int[m];
for (int i = 0; i < m; i++) {
vs[i] = sc.nextInt();
ms[i] = sc.nextInt();
kas[i] = sc.nextInt();
}
System.out.println(max(vMax, mMax, vs, ms, kas));
}
public static int max(int vMax, int mMax, int[] vs, int[] ms, int[] kas) {
int[][] dp = new int[vMax + 1][mMax + 1];
// 种类
for (int i = 0; i < vs.length; i++) {
for (int j = vMax; j >= vs[i]; j--) {
for (int k = mMax; k >= ms[i]; k--) {
dp[j][k] = Math.max(dp[j][k], dp[j - vs[i]][k - ms[i]] + kas[i]);
}
}
}
return dp[vMax][mMax];
}
}1和0
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
>输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 >输出：4 >解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 >其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。>输入：strs = ["10", "0", "1"], m = 1, n = 1 >输出：2 >解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
if (strs == null || strs.length == 0)
return -1;
// 俩包， 0 1
int[][] dp = new int[m + 1][n + 1];
for (String s : strs){
int zeros = 0, ones = 0;
for (char c : s.toCharArray()){
if (c == '0')
zeros++; // 统计数量
else
ones++; // 统计数量
}
// 开始dp
for (int i = m; i >= zeros; i--){
for (int j = n; j >= ones; j--){
// 优化过后的dp
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
}本博客所有文章除特别声明外，大部分为学习心得，欢迎与博主联系讨论