dp练习

//dp[j] : 支付j元 有多少种方式
//答案： dp[w]
//转移方程
//初始化： 
//dp[0]=1 dp[j]=0 

// dp[j]+=dp[j-a[i]] 
// dp[j]%=1000000007;

//2
for(int j=1;j<=w;j++){
	for(int i=1;i<=n;i++){
		if(a[i]<=j) dp[j]+=dp[j-a[i]];
	}
} 
//3
for(int i=1;i<=n;i++){
	for(int j=1;j<=w;j++){
		if(a[i]<=j) dp[j]+=dp[j-a[i]];
	}
} 
//定义 dp[i][j][k]： 
//考虑了前i个物品，花费了j体积，花费了k的重量
// 的火力最大情况
//i -> T[i] V[i] G[i]
//转移方程 
//O(n^3) 500x500x500 1e7
//dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-V[i]][k-G[i]]+T[i])
int ans=0;
for(int i=1;i<=n;i++){
	for(int j=1;j<=v;j++){
		for(int k=1;k<=g;k++){
			if(j-V[i]>=0&&k-G[i]>=0)//防止越界 
			dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-V[i]][k-G[i]]+T[i]);
		}
	}
} 
for(int j=1;j<=v;j++){
	for(int k=1;k>=g;k++){
		ans=max(ans,dp[n][j][k]);
	}
}