题目：LXY 的凑单计划

思路：动态规划。

1. 题目需要LXY自己付钱，因此对于所选的菜的价格总和应该小于s。因此可以枚举最终花的钱S。
2. 对于每道菜，讨论在选择当前这道菜的次数<=x的情况下，花一定的钱所能得到的最大满足感（x=0时需要特判）

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
	//快速输入
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	//快速输出
	static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		String[] s=br.readLine().split(" ");
		int n=Integer.parseInt(s[0]);
		int S=Integer.parseInt(s[1]);
		//记录最后支付钱i的情况下所能得到的最大满足感
		int[] dp=new int[S+1];
		//用户记录选择一道菜不同次数的情况下的最大满足感
		int[] tp=new int[S+1];
		for(int i=0;i<n;i++) {
			s=br.readLine().split(" ");
			int p=Integer.parseInt(s[0]);
			int w=Integer.parseInt(s[1]);
			int x=Integer.parseInt(s[2]);
			if(x==0) {
				//当x==0时，选择当前菜的次数不限，因此可以直接枚举取最大值
				for(int j=p;j<=S;j++) {
					dp[j]=Math.max(dp[j], dp[j-p]+w);
				}
			}
			else {
				//初始化tp
				Arrays.fill(tp, 0);
				//枚举选择当前菜的次数
				for(int j=1;j<=x;j++) {
					//更新最后支付钱k的情况下，选择j次当前菜的情况下的最大满足感
					for(int k=p*j;k<=S;k++) {
						tp[k]=Math.max(tp[k], dp[k-p*j]+j*w);
					}
				}
				//更新元素组
				for(int j=0;j<=S;j++) {
					dp[j]=Math.max(dp[j], tp[j]);
				}
			}
		}
		int ans=-1;
		//枚举最后支付钱为i时，所能得到的最大满足感，更新答案
		for(int i=0;i<=S;i++) {
			ans=Math.max(ans, dp[i]);
		}
		pw.println(ans);
		pw.flush();
	}
}