P2500 - 【DP合集】背包 bound

题面

Description

N 种物品，第 i 种物品有 s i 个，单个重量为 w i ，单个价值为 v i 。现有一个限重为 W 的背包，求能容纳的物品的最大总价值。

Input

输入第一行二个整数 N , W ( N ≤ 1000 , M ≤ 10000) 。

接下来 N 行，每行三个整数 s i,w i,v i ，描述一种物品。

Output

输出一行一个整数，描述能容纳的物品的最大总价值。保证答案不会超过 231−1231−1 。

Sample Input

5 1000

4 20 80

9 50 40

7 50 30

6 30 40

1 20 20

Sample Output

1090

题解

多重背包的裸题

如果直接把每个物品拆成多个'1'的话会超时

需要用到二进制优化，

然后就转化成了01背包。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAX=1050;

int w[MAX*1000];//重量

int v[MAX*1000];//价值

int f[MAX*1000];

int N,M,W,V,S,cnt=0;

inline int read()

{

	  register int x=0,t=1;

	  register char ch=getchar();

	  while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	  if(ch=='-'){t=-1;ch=getchar();}

	  while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}

	  return x*t;

}

int main()

{

      N=read();M=read();

      for(int i=1;i<=N;++i)

      {

      	     S=read();W=read();V=read();

      	     for(int j=1;j<S;j<<=1)//多重背包二进制分解

      	     {

      	     	    v[++cnt]=V*j;

      	     	    w[cnt]=W*j;

      	     	    S-=j;

      	     }

      	     v[++cnt]=S*V;

      	     w[cnt]=S*W;

      }

      N=cnt;//二进制分解之后转换为01背包

      //f[i]表示背包装了重量为i时的最大价值

	  //f[i]=max{f[i-W[j]]+v[j]}

      //利用滚动数组节约内存

	  for(int i=1;i<=N;++i)

	  {

	  	    for(int j=M;j>=w[i];--j)

	  	       f[j]=max(f[j],f[j-w[i]]+v[i]);

	  }

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

	  return 0;

}