[C#]백준 12865 평범한 배낭 - Hide

반응형

https://www.acmicpc.net/problem/12865

문제 요약

배낭에 넣을 수 있는 물건 조합 중에 가치의 최댓값 출력하기

 

 

 

풀이

var R=()=>Console.ReadLine().Split().Select(int.Parse).ToArray();
var a=R(); //a[i] = {물품의 수, 최대 무게}
var b=new int[a[0]][]; //b[i] = {물건의 무게, 가치}
var v=new int[a[1]+1]; //dp[x] = 무게가 x일때의 최대 가치(0~a[1]까지)
for(int i=0;i<a[0];)b[i++]=R(); //한줄씩 입력받기

foreach(var i in b)
    for(int j=a[1];j>=i[0];j--) //같은 물건을 2번 이상 담지 않기 위해 역방향 순회
        v[j]=Math.Max(v[j],v[j-i[0]]+i[1]);
Console.Write(v[a[1]]);

---

더워...