#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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/604018.html