菜鸡求问--趋势科技笔试第二题怎么做？

    public static void main(String[] args) throws InterruptedException {         Scanner scanner = new Scanner(System.in);         int[] num1 = new int[6];         for (int i = 0; i < 6; i++) {             num1[i] = scanner.nextInt();         }         int n1 = scanner.nextInt();         int[][] linkedList = new int[6][1];         for (int i = 0; i < num1.length; i++) {             linkedList[i][0] = num1[i];         }         int process = process(linkedList, n1);         System.out.println(process);     }     public static int process(int[][] num1, int num2) {         if (num2 == 0) {             return 1;         }         if (num2 < 0) {             return 0;         }         int result = 0;         for (int i = 0; i < num1.length; i++) {             int m = 0;             if (num1[i][0] != 0) {                 if (i == 0) {                     m = 1;                 } else if (i == 1) {                     m = 5;                 } else if (i == 2) {                     m = 10;                 } else if (i == 3) {                     m = 20;                 } else if (i == 4) {                     m = 50;                 } else if (i == 5) {                     m = 100;                 }                 num1[i][0] -= 1;             } else {                 continue;             }             result += process(num1, num2 - m);             num1[i][0] += 1;         }         return result;     }

https://leetcode-cn.com/problems/combination-sum-ii/submissions/ 把所有钱币放在一个数组里，感觉就是这道题

unsigned long long solution2(int deep, int* coinNum, int* coinValue,int* coinSum,vector<vector<int>>& dp, int sum) { if (deep == 6) return sum > coinNum[deep] ? 0 : 1; if (dp[deep][sum] > 0 || sum > coinSum[deep]) return dp[deep][sum]; int ans = 0; for (int i = 0; i <= min(sum / coinValue[deep], coinNum[deep]); ++i)  ans += solution2(deep + 1, coinNum, coinValue, coinSum, dp, sum - i*coinValue[deep]); dp[deep][sum] = ans; return ans; } unsigned long long solution3(int deep, int* coinNum, int* coinValue,int * coinSum, vector<vector<int>>& dp, int m) { int ans = 0; for (int i = 0; i <= m; ++i) { if (0 == dp[deep][i])  continue; for (int j = min(i / coinValue[deep], coinNum[deep]); j >= 0; --j) { if (i - j*coinValue[deep] > coinSum[deep + 1]) break; if (deep < 5)  dp[deep + 1][i - j*coinValue[deep]] += dp[deep][i]; else  ans += dp[deep][i]; } } return deep < 5 ? solution3(deep + 1, coinNum, coinValue, coinSum, dp, m) : ans; } int main() { int m = 5000; vector<vector<int>> dp(7, vector<int>(m+1, 0)); int coinValue[7] = { 100,50,20,10,5,2,1 };               //七种硬币面值 int coinNum[7] = { 1000,1000,1000,1000,1000,1000,1000 }; //七种硬币数量 //coinSum[i]表示在index在i-1以后的所有硬币能够凑起来的最大数，比如本例中coinSum[6]=1000,coinSum[5]=3000 int coinSum[7];                              coinSum[6] = coinNum[6] * coinValue[6]; for (int i = 5; i >= 0; --i) coinSum[i] = coinSum[i + 1] + coinNum[i] * coinValue[i]; cout  << solution2(0, coinNum, coinValue, coinSum, dp, m) << endl; vector<vector<int>> dp1(7, vector<int>(m + 1, 0)); dp1[0][m] = 1; cout  << solution3(0, coinNum, coinValue, coinSum, dp1, m) <<  endl;    return 0; }

两套代码solution1，solution2； 复杂度分析： 可以用DP做，这里我提供两个代码。都是基于DP，他们在m等于10000以下，一秒内都可以运行完。solution1在M比较小的时候比solution2快（m不超过十万），复杂度都是m平方。在m比较小的时候（十万以下），solution1明显比2快。（solution1前面的常数小）。 代码解释： solution1 代码中dp 是一个二维数组：dp[index][sum]，index表示第index种货币，sum表示当前需要组合成的数. dp[index][sum] 表示用第大于等于下标为index的硬币组成SUM这个数有多少种方式。 那么可以导出这样一个公式： 式中index 代表硬币的下标。（我的代码里下标为0的硬币是100，下标为1的是50.。。。），value是当前下标硬币的值，num是当前硬币的数量。 我们所要求的的是用下标大于等于0的硬币（就是所有硬币）组成数M的方式有多少种。 solution2: dp 数组仍然是二维数组，dp[index][sum]  中的index，sum意义不变，但是dp[index][sum]本身的意义有很小的变化：dp[index][sum] 代表它被访问的次数。.举个例子：m=101;一种可能的组合 1*100+0*50+0*20+。。。+1*1；还有一种组合 0*100+2*50+。。。+1*1；可以看到，第一种组合为1,0,0,0,0,0,1，第二种为0,2,0,0,0,0,1,他们在在访问第三种硬币的时候，都是要求第二种以后的硬币组合出一个1（因为前两种（下标0,1）已经组合出了100），所以需要后面下标为2,3,4,5,6种硬币组合出1；也就是说dp[2][1]被访问了两次。这样也就是说，我们只需要统计最后一种硬币在所有可能的和上被访问的次数，也就是我们的总次数。   递推公式为： value是index硬币的值，num是数量。 如果不用递归函数，空间复杂度还其实可以优化，因为每个状态只跟上一个状态有关。 具体代码注释下一条。

我需要知道m的大小范围。才能确定复杂度

最后没有时间了，也不知道这个能不能过................ 用的是把所有的钱放到一个数组里，然后dfs加回溯，一旦发现满足条件的，就把组合的size保存起来。 import java.util.ArrayList; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { static int[] coins = {1, 5, 10, 20, 50, 100};     private static String process(String num1, String num2){         String[] arr = num1.split(" ");         int[] nums = new int[arr.length];         for(int i=0;i<coins.length;i++) {          nums[i] = Integer.parseInt(arr[i]);         }         int target = Integer.parseInt(num2);                  ArrayList<Integer> tmp = new ArrayList<>();         for(int j=0;j<nums.length;j++) {      for(int k=0;k<nums[j];k++)      tmp.add(coins[j]);      }                  ArrayList<Integer> res = new ArrayList<>();         ArrayList<Integer> path = new ArrayList<>();         hepler(res, tmp, target, 0, 0, path);         int num = 0;         for(int val:res) {          num += val;         }         return num+"";              }     private static void hepler(ArrayList<Integer> res, ArrayList<Integer> coins, int target, int pos, int sum, ArrayList<Integer> path) { if(sum == target) { res.add(path.size()); return; } if(sum > target) return; Set<Integer> set = new HashSet<>(); for(int i=pos;i<coins.size();i++) { if(set.contains(coins.get(i))) continue; set.add(coins.get(i)); path.add(coins.get(i)); hepler(res, coins, target, i+1, sum+coins.get(i), path); path.remove(path.size()-1); } } public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         String strValueSequences = sc.nextLine();         String strChargeNum = sc.nextLine();         String sum = process(strValueSequences, strChargeNum);         System.out.println(sum);     } }

它是要求组合数还是组合长度呀

回溯可以

暴力搜😂😂暴力一时爽，一直暴力一直爽

以身试法，6层for循环保你AC

将所有银币从小到大组成一个数组，然后去重复的深度优先搜索。

多重背包问题

二维的do应该可以

线上笔试是只有三道编程题么

你的背包

前两题都是leetcode原题

多重背包吧