http://poj.org/problem?id=2184
题意：给定两个属性，求这两个属性的和的最大值.........
思路：将第一个属性往后平移1000个单位，然后推导其动态转移方程，若是dp[i]，代表当加入第一个属性加到i时，符合题意的第二个属性的最大值......题意是两个属性的和的最大值，那么动态转移方程必然不是dp[j]=max(dp[j],dp[j-s[i][0]]+s[i][1]），因为这个动态转移方程固然可以求出第二个属性的最大值，但别忘了题意要求第一个属性与第二个属性的和的最大值，那么，第一个属性平移了1000个单位，在考虑动态转移时，是必须要将这个考虑进去的。可以开一个a数组记录路径，然后根据题意，
动态转移方程应该为dp[j]=max(dp[j]-a[j]*1000,dp[j-s[i][0]]+s[i][1]-(a[j-s[i][0]]+1)*1000),一开始a数组全部赋值为0，所以需要a[j-s[i][0]]+1.....因为它新加入了一个值。考虑这个方程，dp数组的初始全部赋值为负无穷大，dp[0]=0。
注意一点，在历遍查找最大值的时候，dp[i]>0,i-a[i]*1000>0
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define maxx 1000005
int s[maxx][2],dp[maxx],a[maxx];
int main()
{
int n;
while(scanf("%d",&n)>0)
{
int sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d %d",&s[i][0],&s[i][1]);
if(s[i][0]<0&&s[i][1]<0)
{
i--;
n--;
continue;
}
s[i][0]+=1000;
sum+=s[i][0];
}
memset(a,0,sizeof(a));
for(int i=0;i<=sum;i++)
dp[i]=-maxx;
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=sum;j>=s[i][0];j--)
if(dp[j]-a[j]*1000<dp[j-s[i][0]]+s[i][1]-(a[j-s[i][0]]+1)*1000)
{
dp[j]=dp[j-s[i][0]]+s[i][1];
a[j]=a[j-s[i][0]]+1;
}
}
int maxn=0;
for(int i=1;i<=sum;i++)
if(maxn<dp[i]-a[i]*1000+i&&dp[i]>=0&&i-a[i]*1000>=0)
maxn=dp[i]-a[i]*1000+i;
printf("%d
",maxn);
}
return 0;
}