与普通背包不同的地方在于，这里背包的容量是动态的，所以用f[i][j]表示前i件物品中，满足还剩j个挂钩空着的最大愉悦值，就解决了背包容量未知的问题，然后状态转移方程的推导与01背包相似，如果不取第i个，最优解就是f[i-1][j]，如果不取，f[i-1][max(j-a[i],0)+1]+b[i]。因为如果不取这个这个挂饰，挂钩数就只剩下j-a[i]+1个，但这个表达式的值有可能是一个负数，没有意义，所以要取最差的情况，即舍弃所有挂饰，只剩手机上原来的那个挂钩，也就是1个挂钩。
但是有些时候，j-a[i]+1为负数也可能有意义。因为挂钩的位置没有要求，只要后来的挂钩能把j补成非负数就是合法的，但如果去考虑这个，动规的循环变量就不确定，所以要把挂饰按能提供的挂钩数量从大到小排序，就能避免这种情况。
（参考：http://www.cnblogs.com/2014nhc/p/6231288.html）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int f[2111][2111]; 7 8 struct rec 9 { 10 int a,b; 11 }x[2111]; 12 13 int cmp(const rec&x1,const rec&x2) 14 { 15 return x1.a>x2.a; 16 } 17 18 int max(int a,int b) 19 { 20 return a>b?a:b; 21 } 22 23 int main() 24 { 25 int n; 26 scanf("%d",&n); 27 for (int i=1; i<=n; i++) 28 scanf("%d%d",&x[i].a,&x[i].b); 29 sort(x+1,x+n+1,cmp); 30 memset(f,-210000000,sizeof(f)); 31 f[0][1]=0; 32 for (int i=1; i<=n; i++) 33 for (int j=0; j<=n; j++) 34 f[i][j]=max(f[i-1][j],f[i-1][max(j-x[i].a,0)+1]+x[i].b); 35 int ans=0; 36 for (int i=0; i<=n; i++) 37 ans=max(ans,f[n][i]); 38 printf("%d",ans); 39 return 0; 40 }
http://www.lydsy.com/JudgeOnline/problem.php?id=4247
原文：http://www.cnblogs.com/Patrick-X/p/6252720.html