学步园

题目描述

【问题描述】
在《Harry Potter and the Deathly Hallows》中，Harry Potter他们一起逃亡，现在有许多的东西要放到赫敏的包里面，但是包的大小有限，所以我们只能够在里面放入非常重要的物品，现在给出该种物品的数量、体积、价值的数值，希望你能够算出怎样能使背包的价值最大的组合方式，并且输出这个数值，赫敏会非常地感谢你。
出自:宜昌一中
【数据规模】
对于30%的数据
1<=v<=500
1<=n<=2000
1<=m<=10
1<=w<=20
1<=s<=100

对于100%的数据
1<=v<=500
1<=n<=2000
1<=m<=5000
1<=w<=20
1<=s<=100
输入格式

【输入】
（1）第一行有2个整数，物品种数n和背包装载体积v。
（2）2行到n+1行每行3个整数，为第i种物品的数量m、体积w、价值s。.
输出格式

【输出】
仅包含一个整数，即为能拿到的最大的物品价值总和。
样例输入
【输入样例】 2 10 3 4 3 2 2 5
样例输出
【输出样例】 13 【注释】选第一种一个，第二种两个。结果为3*1+5*2=13 

簡單的一道多重背包，不再多說。
注意枚舉的時候，分成兩種情況：
若某個物品數量乘以單位體積超過背包總容量，則當成完全背包處理；否則將這個物品的數量拆成二進制數，再按零壹背包的方式枚舉這個二進制數的每一位。
ACCode：

#include <cstdio>
#include <cstring>
#include <bitset>
#include <cstdlib>

using std::max;

const char fi[] = "rqnoj98.in";
const char fo[] = "rqnoj98.out";
const int maxN = 2010;
const int maxV = 510;
const int MAX = 0x3fffff00;
const int MIN = -0x3fffff00;

int f[maxV];
int a[maxN];
int w[maxN];
int v[maxN];
int n, m;

  void init_file()
  {
    freopen(fi, "r", stdin);
    freopen(fo, "w", stdout);
  }
    
  void readdata()
  {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n + 1; ++i)
      scanf("%d%d%d", a + i, w + i, v + i);
  }
  
  void work()
  {
    for (int i = 1; i < n + 1; ++i)
    {
      if (a[i] * w[i] >= m)
       for (int j = w[i]; j < m + 1; ++j)
        f[j] = max(f[j], f[j - w[i]] + v[i]);
      else
      {
        for (int k = 1; k < a[i]; k <<= 1)
        {
          for (int j = m; j >= k * w[i]; --j)
            f[j] = max(f[j], f[j - k * w[i]]
              + k * v[i]);
          a[i] -= k;
        }
        for (int j = m; j >= a[i] * w[i]; --j)
          f[j] = max(f[j], f[j - a[i] * w[i]]
            + a[i] * v[i]);
      }
    }
    printf("%d", f[m]);
  }
  
int main()
{
  init_file();
  readdata();
  work();
  exit(0);
}