public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt();//输入商品个数 int Max_room = scanner.nextInt();//输入袋子容量 int[] weight = new int[n]; int[] price = new int[n]; int i = 0; while (i < n) weight[i++] = scanner.nextInt(); i = 0; while (i < n) price[i++] = scanner.nextInt(); int[][] dp = new int[n + 1][Max_room + 1]; for (i = 1; i <= n; i++) { for (int j = 1; j <= Max_room; j++) { if (weight[i - 1] > j) {//袋子的容量不够 dp[i][j] = dp[i - 1][j]; } else {//袋子容量足够 dp[i][j] = Math.max(dp[i - 1][j], price[i - 1] + dp[i - 1][j - weight[i - 1]]); } } } System.out.println(dp[n][Max_room]); }
public static int getFirstUnFormedNum(int[] arr) { if (arr == null || arr.length == 0) { return 0; } if (arr.length == 1) {//只有一个元素 ,在区间[min,max]上,如果所有的数都可以被arr的某一个子集相加得到,那么max+1是arr的最小不可组成和; return arr[0] + 1; } int min = arr[0]; int max = arr[0]; for (int i = 1; i < arr.length; i++) { max += arr[i]; min = Math.min(arr[i], min); } int[] dp = new int[max + 1]; for (int i = 0; i <arr.length ; i++) { for (int j = max; j >= arr[i]; j--) { //dp数组从后向前赋值 dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]); } } for (int i = min; i < max; i++) { if (dp[i] != i) return i; } return max + 1; }
import java.util.*; public class Solution { /** * 正数数组中的最小不可组成和 * 输入:正数数组arr * 返回:正数数组中的最小不可组成和 */ public void getNumber(int[] arr,ArrayList<Integer> result,int pos,int sum){ if(pos==arr.length){ return; } for(int i = pos;i<arr.length;i++){ sum += arr[i]; result.add(sum); getNumber(arr,result,i+1,sum); sum -= arr[i]; } } public int getFirstUnFormedNum(int[] arr) { //2种情况: 1.[min,max] 有正数不能被子集相加得到! 返回该 数 // 2.[min,max] 所以正数都能被子集相加得到 返回 max+1 Arrays.sort(arr); int min = arr[0]; int max = arr[0]; ArrayList<Integer> result = new ArrayList<>(); getNumber(arr,result,0,0); for(int i = 1;i<arr.length;i++){ max += arr[i]; } for(int i = min+1;i<max;i++){ if(!result.contains(i)){ return i; } } return max+1; } }
public class Solution { /** * 正数数组中的最小不可组成和 * 输入:正数数组arr * 返回:正数数组中的最小不可组成和 */ public int getFirstUnFormedNum(int[] arr) { int min = Integer.MAX_VALUE; int max = 0; for(int i = 0;i < arr.length;i++){ if(arr[i] < min){ min = arr[i]; } max += arr[i]; } int[] dp = new int[max + 1]; for(int i = 0;i < arr.length;i++){ for(int j = max;j >= min;j--){ if(j >= arr[i]){ dp[j] = Math.max(dp[j],dp[j - arr[i]] + arr[i]); } } } for(int i = min;i <= max;i++){ if(dp[i] != i){ return i; } } return max + 1; } }
public class Solution { /** * 正数数组中的最小不可组成和 * 输入:正数数组arr * 返回:正数数组中的最小不可组成和 */ public int getFirstUnFormedNum(int[] arr) { int min = Integer.MAX_VALUE; int max = 0; for(int i = 0;i < arr.length;i++){ if(arr[i] < min){ min = arr[i]; } max += arr[i]; } boolean[] res = new boolean[max + 1]; res[0] = true; for(int t : arr){ for(int i = max;i >= t;i--){ res[i] = res[i] || res[i - t]; } } for(int j = min;j < res.length;j++){ if(!res[j]){ return j; } } return max + 1; } }
public class Solution { public int getFirstUnFormedNum(int[] arr) { if(arr == null || arr.length == 0) return 1; int min = Integer.MAX_VALUE; int max = 0; for (int i = 0; i < arr.length; i++) { max += arr[i]; min = Math.min(min,arr[i]); } boolean form[] = new boolean[max + 1]; form[0] = true; // 为了使单个元素去求和时是真的 (i + 0 = i) for (int i = 0; i < arr.length; i++) { for (int j = max; j >= arr[i]; j--) { form[j] = form[j - arr[i]] || form[j]; } } for (int i = min; i < form.length; i++) { if(!form[i]) return i; } return max + 1; } }