[DP] 햄버거 다이어트(SWEA 5215번, 자바)

 

 

[KNAPSACK 알고리즘]

-> 목표 무게 이내의 가방 최대 이익 구하기 

import java.util.Scanner;

public class KnapsackTest {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		int N=sc.nextInt(); //가방 개수
		int W=sc.nextInt(); //가방 목표 무게 
			
		int[] weights= new int[N+1];
		int[] profits=new int[N+1];
		
		for(int i=1;i<=N;i++) {
			weights[i]=sc.nextInt();
			profits[i]=sc.nextInt();
		}
		int[][] D=new int[N+1][W+1];
		
		//초기값 세팅:int[][] 배열의 자동 초기화를 이용 
		for(int i=1;i<=N;i++) {
			for(int w=1;w<=W;w++) {
				
				//해당 물건의 무게가 w를 초과하는지 
				if(weights[i] > w) {
					D[i][w]=D[i-1][w];
				}
				else {
					D[i][w]=Math.max(D[i-1][w], profits[i]+D[i-1][w-weights[i]]);
				}
			}
		}
		System.out.println(D[N][W]);
	}

}

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_5215_햄버거다이어트{

	static int N,L;
	static int[] score;
	static int[] cal;
	static int[][] d;
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T=Integer.parseInt(br.readLine());
		
		for(int t_c=1;t_c<=T;t_c++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			N=Integer.parseInt(st.nextToken());
			L=Integer.parseInt(st.nextToken());
			
			score=new int[N+1];  //점수
			cal=new int[N+1]; //칼로리 
			d=new int[N+1][L+1];//해당 칼로리 일 때의 점수 값 
			
			for(int i=1;i<=N;i++) {
				st=new StringTokenizer(br.readLine());
				score[i]=Integer.parseInt(st.nextToken());
				cal[i]=Integer.parseInt(st.nextToken());
				d[i][cal[i]]=score[i];
			}
			
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=L;j++) {
					if(cal[i]>j) d[i][j]=d[i-1][j];
					else
						d[i][j]=Math.max(d[i-1][j],d[i-1][j-cal[i]]+score[i]);
			
				}
			}
		
			System.out.println("#"+t_c+" "+d[N][L]);
		}
	}
}