不想分类讨论的看过来！

//众所周知，01和多重背包其实都可以当作多重背包做
//但是完全背包可以无限选，用多重的方法会爆时间
//怎么办呢？
//注意到完全背包虽然看似可以无限选，但是实际最多只能选到背包容量
//所以对于每物品，实际最多只能选背包最大容量除以该物品的重量
//所以，我们可以用此法将完全背包也转化为多重背包 
//所以，易得： 
#include<iostream>
using namespace std;
string ts,te;
int n,t,k,a,b,c,dp[100010];
struct thing{
	int d,w,p;
}thing[100010];//结构体用来多重背包的二进制优化 
int m(string a){//将时刻转化为分钟 
	int minutes=0,w=1,u=a.size()-1;
	while(a[u--]!=':'){
		minutes+=w*(a[u+1]-48);
		w*=10;
	}//转化分 
	w=1;
	for(int j=u;j>=0;j--){
		minutes+=(a[j]-48)*60*w;
		w*=10;
	}//转化时 
	return minutes;
}
int main(){
	cin>>ts>>te>>n;
    t=m(te)-m(ts);//背包容量 
    for(int i=1;i<=n;i++){
	    cin>>b>>a>>c;
	    if(c==0){
	    	c=t/b;//完全转多重 
		}
	    int h=1;
	    while(c>h){
	    	c-=h;
	    	thing[++k].d=a*h;
	    	thing[k].w=b*h;
	    	h*=2;
		}
		if (c!=0)
		{
			thing[++k].d=c*a;
			thing[k].w=b*c;
		}
	}
	for(int i=1;i<=k;i++){
		for(int j=t;j>=0;j--){
			if(j>=thing[i].w){
			    dp[j]=max(dp[j],dp[j-thing[i].w]+thing[i].d);//正常dp 
			}
		}
	}
	cout<<dp[t];//输出 
	return 0;
}

题意

三种樱花：看一遍(01背包)，看n遍(多重背包)，看无数遍(完全背包)。

思路

将多重背包简化为01背包，然后分为01背包与完全背包讨论两次

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int turn(string a){		//转换为分钟
	int l=a.size(),ans=0;
	if(a[1] != ':') ans+=((a[0]-'0')*10+a[1]-'0')*60;	//时 
	else ans+=(a[0]-'0')*60;
	if(a[l-2] != ':') ans+=a[l-1]-'0'+(a[l-2]-'0')*10;		//分 
	else ans+=a[l-1]-'0';
	return ans;
}

string te,ts;
int n,W;
int ww,vv,p,f[10005];
int w[100005],v[100005],len=0, w_inf[100005],v_inf[100005],len_inf=0;

int main(){
	cin>>ts>>te>>n;
	W=turn(te)-turn(ts); //剩余时间等于上学时间(Te)-现在时间(Ts)，转化成分钟计算
	
	while(n--){
		cin>>ww>>vv>>p;
		if(p == 0){		//完全
			w_inf[++len_inf]=ww;
			v_inf[len_inf]=vv;
		} 
		else if(p == 1){	//01
			w[++len]=ww;
			v[len]=vv;
		} 
		else{    //多重->01
			for(int s=1;s<=p;s*=2){
				w[++len]=ww*s;
				v[len]=vv*s;
				p-=s;
			}
			if(p != 0){
				w[++len]=ww*p;
				v[len]=vv*p;
			}
		}
	}
	
	//分类讨论
	for(int i=1;i<=len;i++){
		for(int j=W;j>=w[i];j--){
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	for(int i=1;i<=len_inf;i++){
		for(int j=w_inf[i];j<=W;j++){
			f[j]=max(f[j],f[j-w_inf[i]]+v_inf[i]);
		}
	}
	cout<<f[W];
	return 0;
}