簡單吃飯（0-1背包）

Description

Input

Output

Sample

代碼

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int total = scanner.nextInt();int price[] = new int[n];int high[] = new int[n];for(int i =0;i<n;i++){price[i] = scanner.nextInt();high[i] = scanner.nextInt();}System.out.println(process(price,high,total));}public static int process(int price[],int high[],int prices){//總計happyint dp[][] = new int[price.length+1][prices+1];for(int i=1;i<=price.length;i++){for(int j=1;j<=prices;j++){dp[i][j]=dp[i-1][j];if(j>=price[i-1]){dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-price[i-1]]+high[i-1]);}}}return dp[price.length][prices];}
}

思路

使用動態規劃，與完全吃飯類似
注意的是dp[i][j]=dp[i-1][j]
這樣是保證選取的食物有序，對食物僅能選取0-1次