腾讯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;
}