学步园

  0-1背包，完全背包，多重背包， 二维费用背包模板

//0-1背包模板(每一件物品只有一件)
void bag01(int cost, int weigth)
{
    for (i=v; i>=cost; i--)
        dp[i] = max(dp[i], dp[i-cost]+weight);
}

/*
hdu 2159 FATE
二维费用的背包问题
有件物品，每一件物品具有两种不同的费用，拥有这支付两种的值为V1和V2
选择一种物品时必须付出两种代价
假设第i件物品所需的代价分别为c1[i]和c2[i],物品的价值为w[i].
状态转移方程为：
f[i][v][u] = max{f[i-1][v][u], f[i-1][v-c1[i]][u-c2[i]]+w[i]}}
*/
//0-1背包
void bag01(int cost1, int cost2, int weight)
{
    for (i=v1; i>=cost1; i--)
        for (j=v2; i>=cost2; j--)
         dp[i][j] = max(dp[i][j], dp[i-cost1][j-cost2]+weigth);
}

//完全背包
void complete(int cost1, int cost2, int weigth)
{
     for (i=cost1; i<=v1; i++)
        for (j=cost2; j<=v2; j++)
         dp[i][j] = max(dp[i][j], dp[i-cost1][j-cost2]+weigth);
}

 hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

<pre name="code" class="cpp">#include <iostream>
#include <cstring>
using namespace std;
#define MAX 2000
#define max(a, b) a > b ? a : b
int dp[MAX];
int p[MAX], h[MAX], c[MAX];//米的：价格 重量 袋数
int n, m;
void bag01(int cost, int weight)
{
    int i;
    for (i=n; i>=cost; i--)
        dp[i] = max(dp[i], dp[i-cost]+weight);
}
void complete(int cost, int weight)
{
    int i;
    for (i=cost; i<=n; i++)
      dp[i] = max(dp[i], dp[i-cost]+weight);
}
int main()
{
    int cnt, i, j;
    int k;
    cin>>cnt;
    while (cnt--)
    {
        cin>>n>>m;
        memset(dp, 0, sizeof(dp));
        for (i=0; i<m; i++)
            cin>>p[i]>>h[i]>>c[i];
        for (i=0; i<m; i++)
        {
            if (p[i]*c[i]>=n)
                complete(p[i], h[i]);
            else
            {
                k = 1;
                while (k<c[i])
                {
                    bag01(p[i]*k, h[i]*k);
                    c[i] -= k;
                    k += k;
                }
                bag01(p[i]*c[i], h[i]*c[i]);
            }
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}