seo怎样优化网站,网站开发开票交税,网络销售推广,网站专题设计软件先说说我的思路吧
下面是部分聊天记录
赤坂 龍之介 2023/12/22 11:06:04 就像我之前说的那样#xff0c;我把每一个药草的价值除以时间#xff0c;得出了新的价值评估标准#xff1a;采摘这个药草时#xff0c;每分钟的价值 赤坂 龍之介 2023/12/22 11:07:00 然后排…
先说说我的思路吧
下面是部分聊天记录
赤坂 龍之介 2023/12/22 11:06:04 就像我之前说的那样我把每一个药草的价值除以时间得出了新的价值评估标准采摘这个药草时每分钟的价值 赤坂 龍之介 2023/12/22 11:07:00 然后排序按照每分钟价值从高到低排若相等则按时间从高到低排 赤坂 龍之介 2023/12/22 11:07:10 从前往后递归 赤坂 龍之介 2023/12/22 11:07:28 第一个只要不超过时间就是必选的 赤坂 龍之介 2023/12/22 11:08:12 第一个选完之后在剩下的里面选同样也是剩下的第一个只要不超过剩余时间也是必选的 赤坂 龍之介 2023/12/22 11:08:25 但是得考虑到时间利用率的问题 赤坂 龍之介 2023/12/22 11:08:44 如你只有70分钟 赤坂 龍之介 2023/12/22 11:09:24 药草14块2分钟 赤坂 龍之介 2023/12/22 11:09:42 药草23块两分钟 赤坂 龍之介 2023/12/22 11:10:09 药草368块68分钟 赤坂 龍之介 2023/12/22 11:10:24 很明显是选2和3是最高的 赤坂 龍之介 2023/12/22 11:10:29 1和3 赤坂 龍之介 2023/12/22 11:10:51 但是按照上面的思路你选完2就不能选3了因为超时 赤坂 龍之介 2023/12/22 11:11:17 所以在第二次选的时候仍然往下看有没有要选的 赤坂 龍之介 2023/12/22 11:11:44 只有价值高于当前价值才可以换第二次选的药草 赤坂 龍之介 2023/12/22 11:13:29 因为下面的药草每分钟的价值都比较低如果价值低于当前药草的价值就不值得选 赤坂 龍之介 2023/12/22 11:14:49 还有一个简单的剪枝如果下面的药草的每分钟价值乘剩下的时间加上之前的价值仍然低于目前的最高的价值结束这一轮的筛选
算是一个不断选择最优的策略
但是得考虑到时间利用率虽然设置了一个目前最大的时间利用率值但是鉴于递归的特点只能看到目前和部分预测下一步无法考虑到全局还是无法完全兼顾所有的情况离最优总是差一点点只能快速地求“次优”
所以WA了
只要解决时间利用率的问题这个算法几乎可以称得上完美
但是我想不出来
代码如下
#includestdio.h
#includestdlib.h
#includemath.h
typedef struct Herb{int t;int v;double v_t;
}Herb;
int cmp(const void * a, const void * b);
void dg(int l_t, int id, int value);
int T, M, maxn, min_l_t;
const double EPS 1e-6;
Herb herb[100];int main(void)
{scanf(%d%d, T, M);min_l_t T;for(int i 0; i M; i){scanf(%d%d, herb[i].t, herb[i].v);herb[i].v_t 1.0 * herb[i].v / herb[i].t;}qsort(herb, M, sizeof(Herb), cmp);dg(T, -1, 0);printf(%d, maxn);return 0;
}
int cmp(const void * a, const void * b)
{if(((Herb *)a)-v_t - ((Herb *)b)-v_t EPS)return -1;else if(fabs(((Herb *)a)-v_t - ((Herb *)b)-v_t) EPS ((Herb *)a)-t ((Herb *)b)-t)return -1;return 1;
}
void dg(int l_t, int id, int value)
{int tmp_v 0;maxn (maxn value) ? maxn : value;min_l_t (min_l_t l_t) ? min_l_t : l_t;for(int i 1; i M - id; i)if((herb[id i].v tmp_v || l_t - herb[id i].t min_l_t) herb[id i].t l_t (l_t * herb[id i].v_t value) - 1.0 * maxn EPS){tmp_v herb[id i].v;dg(l_t - herb[id i].t, id i, value herb[i id].v);}return;
} 有想出来的大佬教我一下 接下来就是动态规划了
我是没想出来问我这题的那个people自己想出来了我就看着他的代码偷师
他的代码如下
#includeiostream
#includestring.h
#includecmath
#includealgorithm
#includeiomanip
using namespace std;
int t, m;
int i, j;
int spend[100]{}, value[100]{};
int most_value 0;
int dp[1000][100];
bool w[1000][100]{};
int culc(int left_time, int i) {if (w[left_time][i]) {return dp[left_time][i];}if (i m) {return 0;}int j;int temp;int mm 0;for (j i; j m; j) {if (spend[j] left_time) {dp[left_time - spend[j]][j 1] culc(left_time - spend[j], j 1);w[left_time - spend[j]][j 1] 1;temp dp[left_time - spend[j]][j 1] value[j];if (temp mm) {mm temp;}}}return mm;
}
int main() {cin t m;for (i 0; i m; i) {cin spend[i] value[i];}cout culc(t, 0) endl;
}引用此代码已获得作者的许可 虽然不知道是部分引用还是全部引用乐
