[BOJ] 7579. app-c++
https://www.acmicpc.net/problem/7579
C++プール
dp[i][c]=アプリケーション1~iのみを考慮し、コストがcの場合の最大メモリ
-バックパック問題のvalue配列=>memory配列、weight配列=>cost配列
-2 D dpアレイで横軸をメモリに設定する場合、横軸として1億->一時費用の合計(和)値を使用します.
C++プール
dp[i][c]=アプリケーション1~iのみを考慮し、コストがcの場合の最大メモリ
-バックパック問題のvalue配列=>memory配列、weight配列=>cost配列
-2 D dpアレイで横軸をメモリに設定する場合、横軸として1億->一時費用の合計(和)値を使用します.
int memory[101];
int cost[101];
int dp[101][10001];//물건 1~i까지만 고려하고 소요 비용이 c일 때의 최대 메모리
using namespace std;
int N,M;
int sum;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for(int i=1;i<=N;i++){
cin>>memory[i];
}
for(int i=1;i<=N;i++){
cin>>cost[i];
sum+=cost[i];
}
for(int i=1;i<=N;i++){
for(int c=0;c<=sum;c++){
if(cost[i]>c) // 물건i를 비활성화 시키는 비용이 임시 비용의 용량을 초과하면
dp[i][c]=(dp[i-1][c]);
else//물건 i를 비활성화 시키는 경우와 시키지 않는 경우 고려
dp[i][c]=max(dp[i-1][c],dp[i-1][c-cost[i]]+memory[i]);
}
}
for (int i = 0; i <= sum; i++)
{
if (dp[N][i] >= M)
{
cout << i << endl;
break;
}
}
}
Reference
この問題について([BOJ] 7579. app-c++), 我々は、より多くの情報をここで見つけました https://velog.io/@mopevxw/BOJ-7579.-앱-cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol