BOJ 7579 앱

www.acmicpc.net/problem/7579

7579번: 앱

 

배낭 문제의 변형이다. 메모리와 비용이 주어지는데 dp테이블을 메모리를 기준으로 채워야 하나?

생각했는데 비용을 기준으로 dp테이블을 채워줘야 한다.

 

예제를 보면 

 

30 10 20 35 40

3 0 3 5 4

 

가 주어지는데 

0   1   2  3   4  5   6   7  8  9   10   11   12  13   14  15

10 10 10 40 50 50 60 80 80 85 100 100 115 115 115 135

이런 식으로 테이블을 채워주고 그때의 m값의 인덱스를 찾아주면 된다.

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, k, sum, w[101], v[101], d[100001];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> w[i];
    for (int i = 0; i < n; ++i) cin >> v[i], sum += v[i];
 
    for (int i = 0; i < n; ++i)
        for (int j = sum; j >= v[i]; --j)
            d[j] = max(d[j], d[j - v[i]] + w[i]);
    
    //for (int i = 0; i <= sum; ++i) cout << d[i] << ' ';
    //cout << endl;
 
    int i;
    for (i = 0; i < sum && d[i] < k; ++i);
    cout << i << endl;
 
    return 0;
}