题目描述

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

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

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

数据范围

0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

样例

Input

4 5
1 2 3
2 4 1
3 4 3
4 5 2

Output

10

算法1

朴素实现

每次枚举使用次数k

时间复杂度

O(nms[i])妥妥超时

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int Max=205;
int N,V;
int v[Max],w[Max],s[Max];
int f[100005];
int main()
{
    scanf("%d%d",&N,&V);
    for(int i=1;i<=N;i++)
    cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=N;i++)
    for(int j=V;j>=0;j--)
    for(int k=1;k<=s[i]&&k*v[i]<=j;k++)
    {
        f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
    }
    cout<<f[V];
    return 0;
}

算法2

二进制优化

其实上述的朴素算法就是将每种物品拆分成了s[i]个，每次枚举。
通过这个idea我们可以尝试进行优化。
我们首先要考虑拆分之后的能表示出的数量是要能够覆盖s[i],但是一定不能超过s[i],
怎么办呢？
这里我们引入二进制优化，
我们发现用 1 2 4 就可以表示出1~7之间所有的数,同时没有超过,
那么我们就可以对一个数进行二进制拆分,将它拆成用二的整次幂来表示,
如果这个数拆分不成整次幂表示?那么可以直接将多余的次数直接使用.
详见代码

时间复杂度

O(nmlog(s[i]))可以过

C++ 代码

//二进制优化多重背包
#include<bits/stdc++.h>
using namespace std;
const int N = 2006;
int n,m;
int f[N];
struct pue{
    int v,w;
};
vector<pue> a;
int k[25];
int main()
{
    scanf("%d%d",&n,&m);
    k[0]=1;
    for(int i=1;i<=20;i++)
    k[i]=(k[i-1])<<1;//预处理
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        scanf("%d%d%d",&v,&w,&s);
        for(int j=0;s>=k[j];j++)
        {
            a.push_back((pue){v*k[j],w*k[j]});
            s-=k[j];
        }
        if(s>0)
        {
            a.push_back((pue){v*s,w*s});
            s=0;
        }
    }
    for(int i=0;i<a.size();i++)
    for(int j=m;j>=a[i].v;j--)
    {
        f[j]=max(f[j],f[j-a[i].v]+a[i].w);
    }
    printf("%d",f[m]);
    return 0;

}