Marcadian’s Blog

Problem. This is a modified knapsack problem. One thing should remember that in real knapsack problem, the order of items doesn’t matter, but in this problem it does. 

Here is sample case:

S = 10

v1 10 9

v2 3 1

If the order like this then you can take both item, but if the order is the reverse you just can take one item. 10 – 3 + 1 < 10. So, what is the best order so that if we take item in that order, we are not lose other items ?

Lemma : Order by B value (input is v a b) descending is optimal ordering.

For example we have 2 items.

v1 a b1

v2 c b2

Where b1 > b2

Proof : Assume that this order is not optimal, then there is strength value, X where

X – a + b1 < c and X – c + b2 >= a

X + b1 < a+c and X + b2 >=  a + c, combine both equation, we have

X + b1 < a + c <= X + b2 , Substract with X

b1 < a + c – X <= b2

b1 < … <= b2, we conclude that b1 < b2 which contradict our assumption, therefore the order by decreasing of B value, is optimal. Here is the code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef struct
{
  int v,a,b;
}item;

bool operator<(item a,item b) { return a.b > b.b; }

int main()
{
  int s,t,n,b,v,a;
  item items[101];
  int best[1001];
  scanf("%d",&t);
  while (t--)
  {
    scanf("%d %d",&s,&n);
    for(int i=1;i<=n;i++)
      scanf("%d %d %d",&items[i].v,&items[i].a,&items[i].b);
    memset(best,-1,sizeof(best));
    sort(items+1,items+1+n);
    best[s] = 0;
    for(int i=1;i<=n;i++)
    {
      a = items[i].a;
      v = items[i].v;
      b = items[i].b;
      for(int j=0;j<=s+b-a;j++)
      {
        int temp = j + a - b;
        if (temp >= a && best[temp]!=-1)
          best[j] =  max(best[temp] + v, best[j]);
      }
    }
    printf("%d\n",*max_element(best,best+1+s));
  }
  return 0;
}