(백준(BOJ)) 앱(#7579)_C++

이 문제의 경우 최대 m바이트 이상이 되는 가장 저렴한 앱 조합을 선택합니다.

백팩 문제로 생각하면 m바이트 이상의 앱을 선택해야 하는데 이때 비용을 최소화해야 한다.

dp(i)(j)는 i번째 앱까지를 고려하여 비용이 j일 때 절약할 수 있는 최대 바이트 수입니다.

dp 배열을 완성한 후, dp(n)

m보다 크거나 같은 j의 첫 번째 선택은 최소 비용입니다.

그러나 dp 배열을 100*10000 배열로 선언할 필요는 없습니다.

재귀 dp 방정식을 고려하면 dp(i)

dp(i -1)은 보존될 때 자신을 제외합니다.

당신은 그것을 볼 수 있습니다.

따라서 2*10000 배열로도 충분히 구현할 수 있습니다.

#include <iostream>

using namespace std;

int n, m, sum;
int mem(101), cost(101);
int dp(2)(10001);

void solve(){
    for(int i=1; i<=n; i++){
        for(int j=0; j<=sum; j++){
            if(j>=cost(i))
				dp(i % 2)(j)=mem(i)+dp(i % 2 == 0 ? 1 : 0)(j-cost(i));

            dp(i % 2)(j)=max(dp(i % 2)(j), dp(i % 2 == 0 ? 1 : 0)(j));
        }
    }
    for(int i=1; i<=sum; i++){
        if(dp(n % 2 == 0 ? 0 : 1)(i)>=m){
            cout << i;
            break;
        }
    }
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    for(int i=1; i<=n; i++)
        cin >> mem(i);
    for(int i=1; i<=n; i++){
        cin >> cost(i);
        sum+=cost(i);
    }
    solve();
}

답변