(알고스팟) 배낭문제(PACKING)(+ 아이템들의 목록도 반환)

public class PACKING {

private static int N;
    private static int dp[][];
    private static int volume[];
    private static int need[];
    private static String name[];
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub

BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

N=6;
name=new String[100];
volume=new int[100];
need=new int[100];
dp=new int[11][N];

for(int i=0;i<N;i++){
String[] line=reader.readLine().split(" ");
name[i]=line[0];
volume[i]=Integer.parseInt(line[1]);
need[i]=Integer.parseInt(line[2]);
}
for(int[] row:dp)
Arrays.fill(row,-1);
int Capacity=10;

System.out.println(PACK(10,0));
}

private static int PACK(int capacity,int item){

if(item==N)return 0;
if(dp[capacity][item]!=-1)return dp[capacity][item];

int ret=PACK(capacity,item+1);

if(capacity>=volume[item])
ret=Math.max(ret,PACK(capacity-volume[item],item+1)+need[item]);

return ret;

}

}

--->>이 문제에서 주의 깊게 보아야 할 것은 다음 item을 선택하느냐 안하느냐 두가지로 나누어 질수 있다.

선택하지 않을 경우는 int ret=PACK(capacity,item+1)로 배낭의 여유분 부피에 변화가 ㅇ벗다. item을 선택하는 경우는 그 아이템의 부피를 뺸 후 만족도 need를 증가시킨다. 단 capacity>=그 아이템 부피 보다 커야 한다.