http://poj.org/problem?id=3624
裸01背包
code:
#include <stdio.h> #define M 13000 #define N 4000 int n, t; int f[M]; int w[N], v[N]; int main() { int i, j, max; scanf("%d%d",&n,&t); for(i=0; i< n; i++) scanf("%d%d",&w[i],&v[i]); for(i=0; i<n; i++) for(j=t; j>=w[i]; j--) if(f[j]<f[j-w[i] ]+ v[i]) f[j] = f[j-w[i]] + v[i]; max = f[0]; for(i=t; i>0; i--) if(max<f[i]) max= f[i]; printf("%d\n",max); return 0; }