【分組背包】HDU 1712 ACboy needs your help

 HDU 1712 ACboy needs your help

題意：N門課程，有M天時間。【每門課程花費1-M天可以獲得的價值不同】，問怎麼選擇花費在每一門上的課程能獲得最大價值，輸出最大價值。

思路：分組背包模闆題

每一門課程的時間選擇都是沖突的，隻能選擇一個。那麼每一門課程就是一個組别，并且天數的選擇是沖突的，隻能選擇一個。就典型的分組背包問題。

第一層循環是枚舉每一個組别 k ；第二層循環是背包容量的枚舉，j 從V->0；第三層循環是枚舉第k個組别的每個物品，如果在j可容納範圍内，就更新目前dp[j]的值為最大{選擇該物品，或不選擇該物品}，就變成是一個01背包問題。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <limits>
#include <set>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#define INF 0x3f3f3f3f
#define MID (l + r) >> 1
#define lsn rt << 1
#define rsn rt << 1 | 1
#define Lson lsn, l, mid
#define Rson rsn, mid + 1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr

#define lowbit(x) x & (-x)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxN = 100 + 5;

int N, M;
struct node{
    int val, cost;
    node(int a = 0, int b = 0): val(a), cost(b) {}
    friend bool operator < (node n1, node n2) { return n1.val > n2.val; }
};
int dp[maxN];
vector<node>vt[maxN];
void init()
{
    for(int i = 0; i <= N; i ++ )
        vt[i].clear();
    for(int i = 0; i <= M; i ++ )
        dp[i] = 0;
}
int main()
{
    while(~scanf("%d%d", &N, &M) && (N || M))
    {
        init();
        for(int i = 1; i <= N; i ++ )
        {
            for(int j = 1; j <= M; j ++ )
            {
                int val; scanf("%d", &val);
                vt[i].push_back(node(val, j));//花費j得到val的價值
            }
        }
        for(int k = 1; k <= N ; k ++ )//枚舉組
            for(int j = M; j >= 0; j -- )//背包容量
            {
                int siz = vt[k].size();
                for(int i = 0; i < siz; i ++ )//屬于第k組的物品标号
                {
                    if(j >= vt[k][i].cost)
                        dp[j] = max(dp[j], dp[j - vt[k][i].cost] + vt[k][i].val);
                }
            }
        printf("%d\n", dp[M]);
    }
    return 0;
}