2023年8月1日发(作者：)
外卖满减,美团笔试题01背包问题题意，每件商品只能买⼀次，⾄少需要买多少钱的东西才能满X元钱。如果我们知道了背包的容量⼤⼩，也就是我们有⼀共多少钱，⽬标就变成了，我们尽可能的买最多的东西，也就是使得总的价值最⼤。我们依次枚举我们钱的⼤⼩（背包⼤⼩），求出背包⼤⼩固定的情况下，最⼤价值。f[i][j]表⽰前i个商品的情况下，背包⼤⼩为j时，能买商品的价格最⼤值。典型01背包问题状态转移：f[i][j]=f[i-1][j], 不选的第i件商品f[i][j] = f[i-1][j-a[i]], j >= a[i] , 背包容量够的情况下选择第i件商品。我们遍历所有状态，求出价格最⼤值⼤于X 中最⼩的价值，就是该问题的答案。import .*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(); int n = t(), x = t(); int[] a = new int[n]; int sum = 0; for(int i=0; i < n; i++) { a[i] = t(); sum += a[i]; } int[][] f = new int[n+1][sum+1]; for(int i=1; i <= n; i++) { for(int j=1; j <= sum; j++) { if(i == 1) { if(j >= a[i-1]) f[i][j] = a[i-1]; continue; } f[i][j] = f[i-1][j]; if(j - a[i-1] >= 0)
f[i][j] = (f[i][j], f[i-1][j - a[i-1]] + a[i-1]); } } //n(String(f)); int res = sum; for(int i=1; i <= n; i++) { for(int j=1; j <= sum; j++) { if(f[i][j] >= x && f[i][j] < res) res = f[i][j]; } } n(res); }}
2023年8月1日发(作者：)
外卖满减,美团笔试题01背包问题题意，每件商品只能买⼀次，⾄少需要买多少钱的东西才能满X元钱。如果我们知道了背包的容量⼤⼩，也就是我们有⼀共多少钱，⽬标就变成了，我们尽可能的买最多的东西，也就是使得总的价值最⼤。我们依次枚举我们钱的⼤⼩（背包⼤⼩），求出背包⼤⼩固定的情况下，最⼤价值。f[i][j]表⽰前i个商品的情况下，背包⼤⼩为j时，能买商品的价格最⼤值。典型01背包问题状态转移：f[i][j]=f[i-1][j], 不选的第i件商品f[i][j] = f[i-1][j-a[i]], j >= a[i] , 背包容量够的情况下选择第i件商品。我们遍历所有状态，求出价格最⼤值⼤于X 中最⼩的价值，就是该问题的答案。import .*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(); int n = t(), x = t(); int[] a = new int[n]; int sum = 0; for(int i=0; i < n; i++) { a[i] = t(); sum += a[i]; } int[][] f = new int[n+1][sum+1]; for(int i=1; i <= n; i++) { for(int j=1; j <= sum; j++) { if(i == 1) { if(j >= a[i-1]) f[i][j] = a[i-1]; continue; } f[i][j] = f[i-1][j]; if(j - a[i-1] >= 0)
f[i][j] = (f[i][j], f[i-1][j - a[i-1]] + a[i-1]); } } //n(String(f)); int res = sum; for(int i=1; i <= n; i++) { for(int j=1; j <= sum; j++) { if(f[i][j] >= x && f[i][j] < res) res = f[i][j]; } } n(res); }}
发布评论