题目描述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

提示：
本题考查多重背包的二进制优化方法。

样例

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

我所认为的原理：

二进制拆分是因为无论目前物品有多少，而二进制代码都可以表示出来，关于dp的最优解无论包含该物品多少份，都可以由拆分的二进制数拼凑而成，所以最优解必定包含于二进制拆分后的物品取舍结果里面；

Tips: 1：如果逻辑没错可是答案出错，有可能是数组已越界；
2：拆分不是把按位的一拿出来拆分，例如该物品有两份，二进制代码为（010），可是若按位拆分则只能
为（两份一起），而dp最优解可能不包含该物品（两份一起）的情况，所以应该从数字（1）开始对其拆分；

C++ 代码

#include<iostream>
#define max(a ,b) ( a > b ) ? a : b
struct kk
{
    int v, w;
}ali[10007];//断点检验是否越界，或者改用vector容器
int N, V, now_idx = 1;
int dp[10001];

int main(void)
{
    scanf("%d %d", &N, &V);

    for (int i = 1; i <= N; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
        for (int m = 1; m <= c; m *= 2)
            ali[now_idx++] = { a * m,b * m }, c -= m;///////////////////二进制优化部分
        if (c > 0)ali[now_idx++] = { a * c,b * c };
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
    }

    for (int i = 1; i < now_idx; i++)
        for (int v = V; v >= ali[i].v; v--)
            dp[v] = max(dp[v], dp[v - ali[i].v] + ali[i].w);
    printf("%d\n", dp[V]);
    return 0;
}