TIOJ 1387 Striker的秘密

[背包問題DP]
網路上有些不錯的資料~不過滿意外的，原來"O(NW)"不算多項式時間@@

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define max(a,b) (a)>(b) ? (a):(b)
struct obj
{
 int w;
 int m;
 int c;
};
int dp[51][10001];
int main()
{
 struct obj objs[51];
 int n;int T;
 scanf("%d",&n);
 for(int ln=1;ln<=n;ln++)
  scanf("%d %d %d",&objs[ln].w,&objs[ln].m,&objs[ln].c);
 scanf("%d",&T);
 for(int ln=1;ln<=n;ln++)
  dp[ln][0]=0;
 for(int lT=0;lT<=T;lT++)
  dp[0][lT]=0;
 for(int ln=1;ln<=n;ln++)
 {
  for(int lT=0;lT<=T;lT++)
  {
   int _max=0;
   if(lT<objs[ln].w)
    dp[ln][lT]=dp[ln-1][lT];
   else
   {
    int _max=0;
    int prc=0;
    while((lT>=prc*objs[ln].w)&&(prc<=objs[ln].c))
    {
     _max>?=dp[ln-1][lT-prc*objs[ln].w]+prc*objs[ln].m;
     prc++;
    }
    dp[ln][lT]=_max;
   }
  }
 }
 printf("%d\n",dp[n][T]);
 return 0;
}