c/c++语言开发共享腾讯2019实习笔试

#include <iostream>  #include <algorithm>  using namespace std;  int main(){  /*现有n种不同的硬币，要组合出1-x的任意面值，问至少需要多少个硬币   * 20 4   * 1 2 5 10   * 输出5   * 贪心求解   * 每次都拿当前可拿的最大的硬币   * */      int x,n;      int coin[1005];      cin>>x>>n;      for(int i=0;i<n;i++){          cin>>coin[i];      }      sort(coin,coin+n);//将硬币有序排列，从小到大        int coinnumber = 0;      int currentmoney = 0;      while(true){          if(currentmoney >= x){              break;          }          else{              for(int i=n-1;i>=0;i--){                  if(coin[i] <= currentmoney+1){  /*   * 当前已经能组成的钱是1到currentmoney，下一个要组成的钱数是currentmoney+1。从不超过currentmoney+1的硬币中取一个值最大的硬币p。   * 这样就能组成范围为1~current+p的钱数了。   * 最开始的时候currentmoney=0，要组成1。选取硬币1，可以组成1~1   * currentmoney=1，要组成2，选取硬币2，可以组成1~1+2   * currentmoney=3,要组成4，选取硬币2，可以组成1~3+2   * currentmoney=5,要组成6，选取硬币5，可以组成1~5+5   *   * */                      coinnumber++;                      currentmoney += coin[i];                      break;                  }              }          }      }        cout<<coinnumber<<endl;      return 0;  }

#include <iostream>  using namespace std;  int main(){      /* 打怪兽，每到一个怪兽，可以贿赂或者不贿赂，贿赂之后就可以带上这个怪兽，到下一个怪兽时如果当前武力值大于怪兽武力值，则不会被攻击。至少需要多少硬币。       * 武力值：8，5，10       * 金币：1，1，2       * 输出：2       * 需要注意的是可带不止一个怪兽       *       * 解法：背包       * dp[i][j] = max(dp[i-1][j],dp[i-1][j-cion[i]]+force[i]);       * 其中dp[i][j]表示包含第i个怪兽的情况下，用j个金币所能获得的最大武力值       * 只不过需要注意两个问题：       * 1、只有满足不贿赂怪兽i时的最大武力值 > 怪兽i的武力值时，才可以不贿赂怪兽i，即dp[i-1][j]       * 2、只有当前金币j大于贿赂怪兽i所需金币coin[i]，并且剩余的金币j-coin[i]可以保证足够贿赂i之前的怪兽时才可以贿赂怪兽i，即dp[i-1][j-coin[i]];       *       * 初始条件：       * dp[0][j]=0;//0个怪兽始终获得武力0       * dp[i][0]=-1;//用0个金币贿赂怪兽不可行       * dp[i][j]=-1;//表示用j个硬币贿赂前i个怪兽不可行。如上面的例子：dp[1][1]=8。dp[3][1]=-1,用1个金币贿赂3个怪兽显然不可行。       *       * 最后一个怪兽n贿赂的情况在dp[n][j];j从小到达增长，如果用j个硬币贿赂n不可行，dp[n][j]=-1，找到第一个不为-1的dp[n][j],这个j即为所求。       *       * */      int n;      cin>>n;      int force[100];      int coin[100];      int dp[101][101];      for (int i = 1; i <= n; ++i) {          cin>>force[i];      }      for (int i = 1; i <=n ; ++i) {          cin>>coin[i];      }      for (int j = 0; j <=100 ; ++j) {          dp[0][j]=0;      }      for (int i = 1; i <=n ; ++i) {          for (int j = 0; j <=100 ; ++j) {              dp[i][j]=-1;          }      }        for (int i = 1; i <=n ; ++i) {//1-n个怪兽          for (int j = 1; j <=100 ; ++j) {//1-100个金币              if (dp[i-1][j] >= force[i]){                  dp[i][j]=max(dp[i][j],dp[i-1][j]);              }              if(j>=coin[i] && dp[i-1][j-coin[i]]!=-1){                  dp[i][j]=max(dp[i][j],dp[i-1][j-coin[i]]+force[i]);              }              //其实就是dp[i][j]=max(dp[i-1][j],dp[i-1][j-coin[i]]+force[i]);只不过加上了限制条件          }      }      int res=0;      for (int j = 1; j <=100 ; ++j) {          if(dp[n][j]!=-1){              res=j;              break;          }      }      cout<<res<<endl;      return 0;  }