寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」部分和問題とその応用たちの解答例

アルゴ式(beta版)の「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」部分和問題とその応用たちからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」部分和問題とその応用たちの解答例

僕が作成、提出したコードは、以下のとおりです。

問題 3:部分和問題

algo-method.com

/*
C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」部分和問題とその応用たちの解答例
問題 3:部分和問題
https://algo-method.com/tasks/309
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    bool dp[n+1][m+1];
    memset(dp,false,sizeof(dp));
    dp[0][0]=true;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            dp[i+1][j]|=dp[i][j];
            if(j>=a[i]){
                dp[i+1][j]|=dp[i][j-a[i]];
            }
        }
    }
    if(dp[n][m]){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}
・問題 4:部分和数え上げ問題

algo-method.com

/*
C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」部分和問題とその応用たちの解答例
問題 4:部分和数え上げ問題
https://algo-method.com/tasks/310
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
const int mod=1000;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            dp[i+1][j]+=dp[i][j];
            dp[i+1][j]%=mod;
            if(j>=a[i]){
                dp[i+1][j]+=dp[i][j-a[i]];
                dp[i+1][j]%=mod;
            }
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}
・問題 5:最小個数部分和問題

algo-method.com

/*
C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」部分和問題とその応用たちの解答例
問題 5:最小個数部分和問題
https://algo-method.com/tasks/311
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
const int big=100000000;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(m+1,big));
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
            if(j>=a[i]){
                dp[i+1][j]=min(dp[i+1][j],dp[i][j-a[i]]+1);
            }
        }
    }
    if(dp[n][m]==big){
        cout<<-1<<endl;
    }else{
        cout<<dp[n][m]<<endl;
    }
    return 0;
}
・問題 6:K 個以内部分和問題

algo-method.com

/*
C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」部分和問題とその応用たちの解答例
問題 6:K 個以内部分和問題
https://algo-method.com/tasks/312
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
const int big=100000000;
int main(void){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(m+1,big));
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
            if(j>=a[i]){
                dp[i+1][j]=min(dp[i+1][j],dp[i][j-a[i]]+1);
            }
        }
    }
    if(dp[n][m]<=k){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}
・問題 7:個数制限付き部分和問題

algo-method.com

/*
C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」部分和問題とその応用たちの解答例
問題 7:個数制限付き部分和問題
https://algo-method.com/tasks/313
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
const int big=100000000;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(m+1,big));
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            if(dp[i][j]<big){
                dp[i+1][j]=0;
            }
            if(j>=a[i]){
                if(dp[i][j-a[i]]<big){
                    dp[i+1][j]=min(dp[i+1][j],1);
                }
                if(dp[i+1][j-a[i]]<b[i]){
                    dp[i+1][j]=min(dp[i+1][j],dp[i+1][j-a[i]]+1);
                }
            }
        }
    }
    if(dp[n][m]==big){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com