思路 数据范围2000

• 从转移方程入手考虑
  • f[i - 1, j] = max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,...,f[i-1,j-sv]+sw)
  • f[i - 1, j - v] = max( f[i-1,j-v], f[i-1,j-2v]+w,...,f[i-1][j-sv]+(s-1)w,f[i-1,j-(s+1)v]+sw)
  • 给出最大值无法求出局部最大值
  • 所以不能用完全背包问题的方式来优化

• 二进制优化
  • 示例
    • 用1，2，4，8…凑出总数，每一个打包的第i个物品可以看成是01背包问题里面的物品，凑出想要的方案数。即用若干个新的物品来表示原来的第i个物品，枚举这若干个物品选或者不选，就可以拼凑出来想要的方案。
    • 本来要枚举1024次，现在只需要枚举10次
    • eg:
    • $o(logn)$

#include <iostream>

using namespace std;

const int N = 12010, M = 2010; //1000*12

int f[N];
int w[N], v[N];
int n, m;

int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ ) 
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }

        if (s > 0)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }    
        n = cnt;

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    printf("%d\n", f[m]);

    return 0;
}