This is my first dynamic programming problem solved by myself from beginning to end...

http://www.algorithmist.com/index.php/UVa_11450

该链接指向此类问题的系统解法

Summary

Given a money M (<= 200) and a list of garments C (<= 20). Each garment has K (<= 20) models. You want to buy one model for each garment and you want to spend your money as much as possible.

Explanation

这是“分组背包”的变体——共C组，每组有K个价格不同物品，每组必选一个物品，求不超过已知数据M的最后总价。

My solution（p.s. 拼搏了整整一天的说，还因为各中bug导致怀疑算法遗漏了什么重要部分T T)

使用滚动数组，F0[left0...M]是已经在处理k-1组时更新完毕的数据，left0标记此时总价最小值（因为每组必选一件）

对于F1，使用left1标记该组最小价值，遍历该组所有物品后将left1加至left0，且将F1全部复制给F0后，F1清零。

F1的遍历从当前输入价格p入手，遍历m = left0+p -> M， F1[m] = max( F0[m-p]+p, F1[m] )

这里的意思是，因为F1中存的是K组加上可能的p后的价格，通过max保证了F1在不超过m的条件下存了最大的价值，又因为F0[0...left0]已经失效，所以从left0+p开始考虑，所以从K组遍历的角度来说状态转移方程是F1[m] = max { F0[m-p_i]+p_i } ( i=1..k )。

综上最终答案是F0[20]，若F0[20]==0，说明left0>M，即总价最低已超过已知数据M，若不为0，则输出。

Implementations

#include <iostream>

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

using namespace std;

void the_case()
{
    int M, C, K, p;
    cin >> M >> C;
    int F0 [M+1]; for (int i=0; i<M+1; i++) F0[i]=0;
    int F1 [M+1]; for (int i=0; i<M+1; i++) F1[i]=0;
    int left0 = 0;
    for(int i=0; i<C; i++)
    {
        cin >> K;
        int left1 = M;
        for(int j=0; j<K; j++)
        {
            cin >> p;
            left1 = min(left1, p);
            for(int m=p+left0; m<M+1; m++)
            {
                F1[m] = max(F0[m-p]+p,F1[m]);
            }
        }
        left0 += left1;
        for(int l=0; l<M+1; l++) F0[l]=F1[l];
        for (int l=0; l<M+1; l++) F1[l]=0;
    }  
    if (F0[M]==0) cout << "no solution" << endl;
    else cout << F0[M] << endl;
}      
       
int main()
{
    int N;
    cin >> N;
    while(N--)
    {
        the_case();
    }
    return 0;
}