题目描述

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

第 i 种物品最多有 s[i] 件，每件体积是 v[i]，价值是 w[i]。

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

输入格式

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

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

输出格式

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

数据范围

0<N,V≤100
0<vi,wi,si≤100

样例

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

我们来连接上文（强烈建议同志们先去看看背包问题1）

根据我们01背包问题引出的动态规划问题思路，先画出我们的“耶路撒冷”

由图可知，我们可以看出图片与完全背包问题十分相类似，so,我们先试试看相同的思路来解题。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N][N];
int w[N],v[N],s[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
            f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

讲解一下：根据题目描述，创建二维数组f[i][j]，i表示体积，j表示物品类型，我们还是抓住“最后”这一关键字，针对i，分为两种大情况，不选i，或选i，不选的表达式写为f[i-1][j]，选i的情况可以细分为选1个，2个.....s[i]个，（注意，我们这里的可选物品的最大数目看的是题目本身的条件，而不是和完全背包问题一样，看体积是否大于0），表达式写为f[i-1][j-v[i]k]+w[i]k。(Ps：我们的代码中没有f[i-1][j]，因为当k=0时，式子就是f(i-1,j))。

但是，我们能用和完全背包问题一样的优化方法吗，答案是否，若将f(i,j-v)展开，因为不是根据体积判断个数的，所以会比完全背包问题多出来一个 。

我们引入一种新的优化方法：打包

我们看一组数据

我们可以根据这组有规律的数字得到任意一个数

假设s=200，我们可以把按之前的规律它分为相似的数据直到64，再加上它的最小大于0的余数73。如此一来，比将200分为1，2，3......200方便很多 。

这便是我们的优化方式，代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int f[N];
int n,m;
int v[N],w[N];
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]);
    }
    cout<<f[m]<<endl;
    return 0;
}

我们将每个数据都按上面的规则分成一块一块的，不但分进v[cnt],w[cnt]中_，注意，此时的下表已经和表示物品种类的i没有关系，cnt仅仅作为计数作用不断扩大_。由此，我们减少的循环次数，节省了时间。