最大价值问题题解

【前言】
无。
【暴力】
枚举每种物品的选择与顺序。
复杂度显然很大。
【正解】
假设我们知道了一个最优解的集合，但不知道顺序。
最优顺序显然是按照代价从小到大排序后依次选择。
因此，我们可以把物品先按代价排序，然后进行动态规划。
设f[i][j]表示在前i个物品中选择了j个的最优答案，注意，这里的物品是按代价排好序的。
转移也就非常显然，f[i][j]可以转移到f[i+1][j]和f[i][j+1]，复杂度是O(n^2)
转移方程太过于简单，相信对大家来说并不难，如果还是有点困难，可以参考给出的代码：

struct nod
{
    int w,v;
}b[6000];
bool cmp(nod x,nod y)
{
    return x.v>y.v;
}
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param a int整型二维数组 
     * @param aRowLen int a数组行数
     * @param aColLen int* a数组列数
     * @return int整型
     */
    int f[6000][6000];
    int wwork(int n, int** a, int aRowLen, int* aColLen) {
        // write code here
    for (int i=1;i<=n;i++) b[i].w=a[i-1][0],b[i].v=a[i-1][1];
    sort(b+1,b+n+1,cmp);
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=i;j++) 
        {
            f[i][j]=max(f[i-1][j],f[i-1][j-1]-b[i].v*(j-1)+b[i].w);
            ans=max(ans,f[i][j]);
        }
    }
    return ans;
    }
};