多重背包-动态规划（2）

汶川大地震——HDU 2191

简单的多重背包

时间不多最近拖拖拉拉暂时没时间再深入理解动态规划了把这个改成01背包简单贴一下代码。。。

埋下了这样的坑

# include<iostream>
# include<algorithm>
# include<cstring>

using namespace std;

//n,m,p,h,c

int dp[105];

int p[105], h[105], c[105];

int n, m;

void mul_bag()
{
    memset(dp,0,sizeof(dp));//初始化非常重要！！

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= c[i]; j++)
            for (int k = n; k >= p[i]; k--)
            {
                dp[k] = max(dp[k],dp[k-p[i]]+h[i]);
            }
}

int main()
{
    int C;

    cin >> C;

    for (int i = 0; i < C; i++)
    {
        cin >> n >> m;

        for (int j = 1; j <= m; j++)
        {
            cin >> p[j] >> h[j] >> c[j];
        }

        mul_bag();

        cout << dp[n] << endl;
    }

    return 0;
}

多重背包-动态规划（2）

推荐阅读