价格的可能性题解

【前言】
非常简单的动态规划题。

【暴力】
搜索，搜出所有可能性。

【不完美的超时做法】
设f[i][j][k]表示，只买前i种商品，共买了j件，能否达到价钱k。
可以转移到f[i+1][j][k]和f[i][j+1][k]
复杂度是O(nm^2*max(v))极限是500^4

【正解】
考虑优化dp。
这里有个小小的技巧。
将所有物品的价格排序，然后减去最小的，这样的作用是，假设我们选的物品个数不足m个，那么可以默认为不足部分全部选择了最小的那一个，我们就可以省去一维，则复杂度变成了O(nm^2*max(v))

参考代码：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param b int整型一维数组 
     * @param bLen int b数组长度
     * @return long长整型
     */
    int a[250010],f[250010];
    long long wwork(int n, int m, int* b, int bLen) {
        // write code here
    for (int i=1;i<=n;i++) a[i]=b[i-1];
    sort(a+1,a+n+1);
    for (int i=2;i<=n;i++) a[i]=a[i]-a[1];
    int mn=a[1];
    a[1]=0;
    int mx=a[n]*m;
    for (int i=1;i<=250000;i++) f[i]=600;
    for (int i=1;i<=n;i++)
    {
        if (a[i]==a[i-1]) continue;
        for (int j=a[i];j<=mx;j++) f[j]=min(f[j],f[j-a[i]]+1);
    }
    long long ans=0;
    for (int i=0;i<=mx;i++) 
    {
        if (f[i]<=m) 
        {
            ans=ans+i+m*mn;
            //printf("%d ",i+k*mn);
        }
    }
    return ans;
    }
};