Question

16-1 找换硬币

a）每次都尽量选最大的、

c）1 4 5

d）找换 i 分钱的最少硬币数是 ans[i]，ans[i] = max{ans[i-s[j]]+1}

#include <iostream>
#include <algorithm>
using namespace std;
//用于排序
bool cmp(int a, int b)
{
  return a < b;
}
int main()
{
  int n, k, i, j;
  //输入数据
  cin>>n>>k;
  int s[100], ans[100];
  for(i = 0; i < k; i++)
    cin>>s[i];
  //对硬币从小到大排序
  sort(s, s + k, cmp);
  //找换 i 分钱的最少硬币数是 ans[i]
  memset(ans, 0, sizeof(ans));
  //ans[i] = max{ans[i-s[j]]+1}
  for(i = 1; i <= n; i++)
  {
    for(j = 0; s[j] <= i; j++)
    {
      if(ans[i] == 0 || ans[i-s[j]]+1 < ans[i])
        ans[i] = ans[i-s[j]]+1;
    }
  }
  cout<<ans[n]<<endl;
  return 0;
}

16-2 最小化平均结束时间的调度

a）每当一个任务执行完时，就选则剩下的任务中选择执行时间最短的任务执行

b）每当一个任务执行完时，就选则剩下的任务中选择剩余执行时间最短的任务执行，每当一个新的任务到来时，如果它的执行时间比当前任务的剩余执行时间要短，就抢占