만두 가게 사장 박승원 C++ - 백준 14855

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

비슷한 문제:백준 동전

꼼꼼히 살피지 않아 많이 틀린 문제.

기본적인 배낭문제의 형태를 띄고 있으나,

이 문제는 Bounded Knapsack Problem으로 알려져있다.

Bounded Knapsack Problem은 0-1 Knapsack과는 다르게

물건들의 개수가 정해져있는 상태이다.

따라서 이를 고려해서 코드를 작성해야 한다.

틀린 부분

1. 불가능한 경우 판별 안함
2. 어떤 밀가루 수 $j$에서 항상 그 만두를 다 만드는 경우만 탐색함

이를 보완해서 작성한 코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,ans=0;
    cin >> n >> m;
    vector<int> a(m+1,1),b(m+1),c(m+1),d(m+1);
    vector<vector<int>> dp(m+1,vector<int> (n+1,0));
    cin >> c[0] >> d[0];
    for(int i=1;i<=m;i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
    for(int i=1;i<=n;i++){
        if(i%c[0]==0){dp[0][i]=i/c[0]*d[0]; ans=max(ans,dp[0][i]);}
    }
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){
        int cnt=min(j/c[i],a[i]/b[i]);
        dp[i][j]=dp[i-1][j];
        for(int k=1;k<=cnt;k++){
            if(j!=k*c[i] && dp[i-1][j-k*c[i]]==0) continue;
            dp[i][j]=max(dp[i-1][j-k*c[i]]+k*d[i],dp[i][j]);
            ans=max(ans,dp[i][j]);
        }
    }
    cout << ans;
    return 0;
}