多重背包二进制拆分

原题链接

把次数进行二进制拆分，因为任何数都可以转化为二进制数

把每一个物品拆成很多个，分别计算价值和所需时间，再转化为01背包求解(这个意思是说要逆序遍历第二层 for 循环)。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
#define re register int
#define maxn 1000000
const int N=1e4+5;
const int T=1005;
int n,hs,ms,he,me,tot;
int t[N],c[N],p[N]; //t:时间 c:美学值 p:次数
int dp[T];
int t1[maxn],c1[maxn]; //用来存储分割后的t*p,c*p
int tp; //t1,c1的索引指针(可共用一个，因为是同步的)
inline void seg(){ //二进制划分
    //对p[i]进行二进制划分，然后分别存储p[i]各个部分与t和p的乘积
    //因为时间和美学值的计算方式都是t*p,c*p
    for(re i=1;i<=n;++i){
        int tmp=1;
        while(p[i]>=tmp){
            p[i]-=tmp;
            t1[++tp]=tmp*t[i],c1[tp]=tmp*c[i];
            tmp<<=1;
        }
        if(p[i]) t1[++tp]=p[i]*t[i],c1[tp]=p[i]*c[i];
    }
}
int main(){
    scanf("%d:%d %d:%d %d",&hs,&ms,&he,&me,&n);
    int tot=(he*60+me)-(hs*60+ms);
    for(re i=1;i<=n;++i){
        scanf("%d%d%d",&t[i],&c[i],&p[i]);
        if(!p[i]) p[i]=T;  //无穷次，但是最大次数不会超过总时间，不然一定不会选到这个次数
    }
    seg();
    for(re i=1;i<=tp;++i)
        for(re j=tot;j>=t1[i];--j)
            dp[j]=max(dp[j],dp[j-t1[i]]+c1[i]);
    printf("%d\n",dp[tot]);
    return 0;
}

这题其实是混合背包问题，也可以用混合背包的方法去做。

• 有限次数
• 无限次数

for(int i=1;i<=n;++i){
  if(p[i]==0){ //完全背包
    for(int j=t[i];j<=tot;++j) dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
  }else{ //01背包
    for(int k=1;k<=p[i];++k) //重复p[i]次01背包的结果就相当于最多取p[i]个的多重背包
      for(int j=tot;j>=t[i];--j)
        dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
  }
}