求解答。 7.15华为笔试题

没有参加考试，看到题目自己练习一下（不确定能否通过所有测例）。 第一道不容易想，学习背包九讲 https://anivian.github.io/pack-master/V2.pdf 第二道也是背包吧，但没学背包，努力往DP上想，差不多也可以想到。

贴一个大佬指导的多重背包解法：

第一题限制了金币数量，并且保证有解，币值都为质数，所以直接贪心应该就可以。 这里再补充一个给定不同面额金币，给定总金额，凑成总金额所需的最少的硬币个数的动态规划解法。 第二题，步长互异且先短后长，先将步长排序，dfs回溯即可。 仅供参考。

第二题可以转为完全背包问题。 用f[i][j]表示从1~i个物品中选，总价格为j，值为当前选法最少的物品数量。 因此f[i][j] = min(f[i-1][j], f[i-1][j-w[i]]+1,...,f[i-1][j-k*w[i]]+k) 由于f[i][j-w[i]]=min(        f[i-1][j-w[i],...,f[i-1][j-k*w[i]+k-1) 有f[i][j] = min(f[i-1][j], f[i][j-w[i]]+1) ```java     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int[] w = new int[n+1];         for (int i = 1; i <= n; i++) {             w[i] = sc.nextInt();         }         Arrays.sort(w);         int v = sc.nextInt();         int[] f = new int[v + 1];         for(int i = 1; i <=v ;i++) f[i] = i;         for (int i = 1; i <= n; i++) {             for (int j = w[i]; j <= v; j++) {                 f[j] = Math.min(f[j], f[j - w[i]] + 1);             }         }         System.out.println(f[v]);     } ```

不知道能不能通过样例 第二题： int dfs(int n, vector<int> costs, vector<int> nums) {     vector<int> dp(n+1, INT_MAX);     dp[0] = 0;     for(int i=0; i<n; i++)     {         for(int j=0; j<5; j++)         {             for(int k=0; k<=nums[j]; k++)             {                 if(dp[i]!=INT_MAX && i+k*costs[j]<=n)                     dp[i+k*costs[j]] = min(dp[i]+k, dp[i+k*costs[j]]);             }         }     }     return dp[n]; } 第三题： int dfs(int n, vector<int> nums) {     sort(nums.begin(), nums.end());     int m = nums.size();     vector<int> dp(n+1, 0);     dp[0] = 1;     for(int i=0; i<m; i++)     {         for(int j=1; j<=n; j++)         {             if(j-nums[i]>=0)                 dp[j] += dp[j-nums[i]];         }     }     return dp[n]; }

第三题回溯吧？

第二题是多重背包转01背包解，因为钱要用完所以状态初始值以及状态转移需修改及判断；第三题是dfs，不过搜的时候判断下一节点》=上一节点，避免超时

全都是背包问题，骚年，回去好好看书吧

第三题可以记录下上一步的位置和步长，满足每一步走的步长单调不减就可以保证不重复了

我靠 7月15的那么难的吗

第一题 贪心+回溯 第二题 递归 转换为求指定和问题 并且当前步伐应该大于等于上一次步伐

第1题使用回溯+贪心方法可以做出来

第三题使用递归！当然也可以改为动态规划！

第二题使用贪心算法，每次从最高价格开始取，花不完的话，又回溯！！直到第一次遇到花完！！肯定是最少得

2是典型的有价值背包问题啊

请教了一下ACM大佬，第2题确实应该是多重背包问题，但是我太菜写不出正解代码😂

 public int change(int amount, int[] coins) {     int len=coins.length;     int[] res=new int[amount+1];     res[0]=1;     for(int coin:coins){         for(int i=1;i<=amount;i++){             if(i>=coin){                 res[i]+=res[i-coin];             }         }     }     return res[amount];     }

第一题背包和bfs都可以&nbsp;放个bfs的代码

楼主参加的华为校招的笔试吗？哪个城市什么岗位啊

2题贪心+回溯，贪心确保数量尽可能少，回溯用来找钱正好花光的方法。 3题完全背包