[BAE/<JOON> 문제풀이] 7579. 앱

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

7579번: 앱

가방(갯수제한 문제)

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
//0/1 knapsack prob
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> w;
    vector<int> cost;
    vector<vector<int>> dp;
    w.resize(n + 1);
    cost.resize(n + 1);
    dp.resize(n + 1);        
    for (int i = 1; i <= n; i++) {        
        cin >> w[i];        
    }    
    for (int i = 0; i <= n; i++) {
        dp[i].resize(n * 100 + 1);
    }    
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];        
    }    

    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (w[i] > w[j]) {
                int t = w[i];
                w[i] = w[j];
                w[j] = t;
                t = cost[i];
                cost[i] = cost[j];
                cost[j] = t;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n * 100; j++) {
            dp[i][j] = 0;
        }
    }

    for (int k = 0; k <= n * 100; k++) {        
        int mx = -1;
        for (int i = 1; i <= n; i++) {            
            for (int j = 0; j <= k; j++) {
                if (dp[i][j] != 0) continue;        
                if (cost[i] <= j) {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + w[i]);
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            if (mx < dp[i][k]) mx = dp[i][k];
        }
        cout << "\n";
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                cout << dp[i][j] << " ";
            }
            cout << "\n";
        }
        if (mx >= m) {
            cout << k;
            return 0;
        }
    }
    cout << "not found";
    return 0;
}