luogu2744 量取牛奶

题目大意

　　给出一个整数集合$A$，总数$N$，规定一个整数序列$\{a_n\}, \forall i, a_i\in A$满足条件：存在一个正整数序列$\{k_n\}$，使得$\sum_{i=1}^n a_i k_i = S$。求$n$最小值且字典序最小的$a_i$。

题解

错误解法

　　令$f(j)$表示使得$\sum_{i=1}^m a_i k_i = j$的最小的$m$的值，令$i$为第几个$A$中的整数，则刷表递推式方式为UpdateMin$(f(j+A_i k),f(j)+1)$。这时我想，如果把$A$中的元素从小到大排序，只有能将以后的状态更新成最小时才更新答案，那么记录到的决策必然就是字典序最小的了。这样就错了，因为如果组成$j_1+K_1 A_{i_1}=j_2+K_2A_{i_2}=S$，$i_1 < i_2$，我们无法证明组成$j_1$的元素的字典序就比$j_2$的小。反例很难容易得出。

正确解法

　　对每个$n$枚举$a_i$为$N$内的组合，然后用完全背包判断选择的组合是否满足条件即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int MAX_OBJ = 150, MAX_V = 21000;

int TotObj, TotV;

int Vs[MAX_OBJ];

vector<int> Ans;

bool DP(int *_vs)

{

    static bool f[MAX_V], vis[MAX_V];

    memset(f, false, sizeof(f));

    f[0] = true;

    for (int i = 1; i <= TotObj; i++)

    {

    	if (!_vs[i])

    		continue;

        memset(vis, false, sizeof(vis));

        for (int j = 0; j <= TotV; j++)

        {

            if (f[j] && !vis[j])

            {

                for (int k = 1; k <= (TotV - j) / _vs[i]; k++)

                {

                	f[j + k * _vs[i]] = true;

                }

            }

        }

    }

    return f[TotV];

}

void JudgeAns(vector<int>& chosen)

{

    static int _vs[MAX_OBJ];

    memset(_vs, 0, sizeof(_vs));

    for (unsigned int i = 0; i < chosen.size(); i++)

        _vs[chosen[i]] = Vs[chosen[i]];

    if (DP(_vs))

        Ans = chosen;

}

void Comb(vector<int>& chosen, int n, int m, int begin, void (*doSth)(vector<int>&))

{

    if (n - begin + 1 < m - chosen.size())

        return;

    if (chosen.size() == m)

    {

        doSth(chosen);

        return;

    }

    for (int i = begin; i <= n; i++)

    {

        if (Ans.size())

            return;

        chosen.push_back(i);

        Comb(chosen, n, m, i + 1, doSth);

        chosen.pop_back();

    }

}

int main()

{

    scanf("%d%d", &TotV, &TotObj);

    for (int i = 1; i <= TotObj; i++)

        scanf("%d", Vs + i);

    sort(Vs + 1, Vs + TotObj);

    vector<int> chosen;

    for (int i = 1; i <= TotObj; i++)

    {

        Comb(chosen, TotObj, i, 1, JudgeAns);

        if (Ans.size())

            break;

    }

    printf("%d ", (int)Ans.size());

    for (unsigned int i = 0; i < Ans.size(); i++)

        printf("%d ", Vs[Ans[i]]);

    printf("\n");

    return 0;

}