二进制拆分

做法：把每一个物品根据2的多少次方拆分，因为任何数都可以转化为二进制数

核心思想：把每一个物品拆成很多个，分别计算价值和所需时间，再转化为01背包求解

最后一点：完全背包可以把他的空间记为999999，不要太大，一般百万就足够了

还有一点：cin和scanf不可以混用

代码

#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
inline void read(int &x) {
	x=0;
	short flag=1;
	char c = getchar();
	while(c<'0'||c>'9') {
		if(c=='-')flag=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x << 3)+ (x << 1)+(c ^ 48);
		c=getchar();
	}
	x*=flag;
}
inline void write(int x) {
	if(x<0) {
		putchar('-');
		x=-x;
	}
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
int h,h1,m,m1,n,dp[1000010],vi,wi,pi,len=1,t=1,v[1000010],w[1000010];
int main() {
	scanf("%d:%d %d:%d %d",&h,&m,&h1,&m1,&n);
	int tim=(h1*60+m1)-(h*60+m);
	//cout<<time<<"\n";
	for(int i=1;i<=n;i++){
		cin>>wi>>vi>>pi;
		t=1;
		if(pi==0) pi=9999999;
		while(pi>t){
			v[len]=t*vi;
			w[len]=t*wi;
			pi-=t;
			t*=2;
			len++;
		}if(pi>0){
			v[len]=pi*vi;
			w[len]=pi*wi;
			len++;
		}
	}
	for(int i=1;i<len;i++){
		for(int j=tim;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	printf("%d",dp[tim]);
	return 0;
}