hdu2191 悼念512汶川大地震 ——多重背包

link:http://acm.hdu.edu.cn/showproblem.php?pid=2191 最简单的那种

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
int n, V, t, f[111], c[111], w[111], m[111];
void zeropack(int c, int w)
{
    for (int v=V; v>=c; --v)
    {
        f[v]=max(f[v],f[v-c]+w);
    }
    return;
}
void completepack(int c, int w)
{
    for (int v=c;v<=V;++v)
        f[v]=max(f[v],f[v-c]+w);
    return;
}
void multipack(int c, int w, int m)
{
    if (c*m >= V)
    {
        completepack(c,w); return;
    }
    int k=1;
    while (k<m)
    {
        zeropack(c*k,w*k); m-=k; k*=2;
    }
    zeropack(c*m,w*m);
    return;
}
int main(void)
{
    ios::sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    int t; cin>>t;
    while (t--)
    {
        cin>>V>>n;
        for (int i=0;i<n;++i) cin>>c[i]>>w[i]>>m[i];
        memset(f,0,sizeof(f));
        for (int i=0;i<n;++i)
        {
            multipack(c[i],w[i],m[i]);
        }
        cout<<f[V]<<endl;
    }
    return 0;
}

其实这种动态规划题目还是要注意初始化，想想问什么这样初始化。