悼念512汶川大地震遇难同胞——珍惜现在,感恩生活--hdu2191(多重背包模板)

时间:2021-08-05 18:43:58

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2191

标准的多重背包

题目

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

基本算法

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值,则有状态转移方程:

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

复杂度是O(V*Σn[i])。

转化为01背包问题

另一种好想好写的基本方法是转化为01背包求解:把第i种物品换成n[i]件01背包中的物品,则得到了物品数为Σn[i]的01背包问题,直接求解,复杂度仍然是O(V*Σn[i])。

但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想,我们考虑把第i种物品换成若干件物品,使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外,取超过n[i]件的策略必不能出现。

方法是:将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。

 

 

悼念512汶川大地震遇难同胞——珍惜现在,感恩生活--hdu2191(多重背包模板)悼念512汶川大地震遇难同胞——珍惜现在,感恩生活--hdu2191(多重背包模板)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>

using namespace std;

#define met(a, b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3f
#define N 2310


int c[N], w[N], k;

void slove(int cost, int weight, int cnt)///二进制思想,把cnt分成1,2,4,8,16......存入c中和w中,//按01背包处理
{
    int m = 1;
    while( cnt >= m)
    {
        c[k] = m*cost;
        w[k++] = m*weight;
        cnt -= m;
        m = m*2;
    }
    if(cnt>0)
    {
        c[k] = cnt*cost;
        w[k++] = cnt*weight;
    }
}

int main()
{
    int T, V, n;

    int cost, weight, cnt, dp[N];

    scanf("%d", &T);

    while(T--)
    {
        met(dp, 0);

        met(c, 0);

        met(w, 0);

        k = 1;

        scanf("%d %d", &V, &n);

        for(int i=1; i<=n; i++)
        {
            scanf("%d %d %d", &cost, &weight, &cnt);

            slove(cost, weight, cnt);
        }
        for(int i=1; i<k; i++)
        {
            for(int j=V; j>=c[i]; j--)
            {
                dp[j] = max(dp[j], dp[j-c[i]]+w[i]);
            }
        }
        printf("%d\n", dp[V]);
    }
    return 0;
}
View Code