解题思路:
本题属于0/1背包问题,具体思路说不上,只需要记住两个公式即可
背包问题只考虑两种情况:采药/不采
dp[i][j],其中i代表第i个物品,j代表剩余时间;(用于统计最后的数据)
cost[],采所花费的时间
value[],采所得到的价值
若采:dp[i][j]=dp[i-1][j-cost[i]]+value[i] 需要剩余时间>=所花费的时间
不采:dp[i][j]=dp[i-1][j]
最后通过公式代入for循环即可
注意事项:
参考代码:
#include<iostream>
using namespace std;
#include<cstring>//数组归零头文件
//#include<algorithm>//排序头文件
int main()
{
int T, M;//总时间/山洞草药数木
cin >> T >> M;
int cost[110] = {0};//采药花费的时间
int value[110] = {0};//所采药材的价值
int dp[110][1010];//统计结果(药材总数目,药材总时间)
memset(dp, 0, sizeof(dp));//数组归零
for (int i = 1; i < M + 1; i++)
cin >> cost[i] >> value[i];
for(int i=1;i<M+1;i++)
for (int j = 1; j < T + 1; j++)
{
if (j >= cost[i])//剩余时间>所需时间
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + value[i]);//比较采/不采
else//剩余时间不够
dp[i][j] = dp[i - 1][j];//不采
}
cout << dp[M][T];//输出
return 0;
}
0.0分
0 人评分
点我有惊喜!你懂得!浏览:1231 |
简单的a+b (C语言代码)浏览:729 |
C语言训练-排序问题<1> (C语言代码)浏览:1353 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:591 |
【蟠桃记】 (C语言代码)浏览:669 |
WU-printf基础练习2 (C++代码)浏览:2007 |
WU-拆分位数 (C++代码)浏览:790 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:1436 |
用筛法求之N内的素数。 (C语言代码)浏览:680 |
C二级辅导-进制转换 (C语言代码)浏览:680 |