#include <stdio.h>
#include <stdlib.h>
typedef struct{
int Wi;
int Vi;
}bag;
bag thing[101]={};
int memo[10002][102]={};
int n;
int put(int i,int W){
if(W < 0)
return -10000;
if(memo[W][i] != 0)
return memo[W][i];
if(W == 0)
return 0;
if(i == n)
return 0;
int a = thing[i].Vi + put(i+1,W-thing[i].Wi);
int b = put(i+1,W);
if(a >= b){
memo[W][i] = a;
return a;
}
else{
memo[W][i] = b;
return b;
}
}
int main(){
int W;
scanf("%d %d",&n,&W);
for(int i=0;i<n;i++){
scanf("%d %d",&thing[i].Wi,&thing[i].Vi);
}
printf("%d",put(0,W));
}
top of page

기능을 테스트하려면 라이브 사이트로 이동하세요.
수정: 2024년 2월 28일
베낭 문제
베낭 문제
댓글 0개
좋아요
댓글(0)
bottom of page