寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「動的計画法」部分和問題とナップサック問題の解答例

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

C++による「動的計画法」部分和問題とナップサック問題の解答例

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

Q3-1. 部分和問題 (導入編)

algo-method.com

/*
C++による「動的計画法」部分和問題とナップサック問題の解答例
Q3-1. 部分和問題 (導入編)
https://algo-method.com/tasks/336
提出コードの解答例
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-1);
    for(int i=0;i<n-1;i++){
        cin>>a[i];
    }
    vector<vector<bool>> dp(n,vector<bool>(m,false));
    dp[0][0]=true;
    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            if(dp[i][j]==false){
                continue;
            }
            dp[i+1][j]=true;
            if(j+a[i]<m){
                dp[i+1][j+a[i]]=true;
            }
        }
    }
    int ans=0;
    for(int i=0;i<m;i++){
        if(dp[n-1][i]){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
・Q3-2. 部分和問題

algo-method.com

/*
C++による「動的計画法」部分和問題とナップサック問題の解答例
Q3-2. 部分和問題
https://algo-method.com/tasks/337
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> w(n);
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    vector<vector<bool>> dp(n+1,vector<bool>(m,false));
    dp[0][0]=true;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            if(dp[i][j]==false){
                continue;
            }
            dp[i+1][j]=true;
            if(j+w[i]<=m){
                dp[i+1][j+w[i]]=true;
            }
        }
    }
    if(dp[n][m]){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}
・Q3-3. ナップサック問題 (導入編)

algo-method.com

/*
C++による「動的計画法」部分和問題とナップサック問題の解答例
Q3-3. ナップサック問題 (導入編)
https://algo-method.com/tasks/341
提出コードの解答例
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-1),b(n-1);
    for(int i=0;i<n-1;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-1;i++){
        cin>>b[i];
    }
    vector<vector<int>> dp(n,vector<int>(m,-1));
    dp[0][0]=0;
    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            if(dp[i][j]<0){
                continue;
            }
            dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
            if(j+a[i]<m){
                dp[i+1][j+a[i]]=max(dp[i+1][j+a[i]],dp[i][j]+b[i]);
            }
        }
    }
    cout<<dp[n-1][m-1]<<endl;
    return 0;
}
・Q3-4. ナップサック問題

algo-method.com

/*
C++による「動的計画法」部分和問題とナップサック問題の解答例
Q3-4. ナップサック問題
https://algo-method.com/tasks/329
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> w(n),v(n);
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(m+1,-1));
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            if(dp[i][j]<0){
                continue;
            }
            dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
            if(j+w[i]<=m){
                dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
            }
        }
    }
    int ans=-1;
    for(int i=0;i<=m;i++){
        ans=max(ans,dp[n][i]);
    }
    cout<<ans<<endl;
    return 0;
}
・Q3-5. 部分和問題 (応用 1)

algo-method.com

/*
C++による「動的計画法」部分和問題とナップサック問題の解答例
Q3-5. 部分和問題 (応用 1)
https://algo-method.com/tasks/350
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
#define INF 100000000
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> w(n);
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(m+1,INF));
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=m;j++){
            if(dp[i][j]==INF){
                continue;
            }
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
            if(j+w[i]<=m){
                dp[i+1][j+w[i]]=min(dp[i+1][j+w[i]],dp[i][j]+1);
            }
        }
    }
    if(dp[n][m]==INF){
        cout<<-1<<endl;
    }else{
        cout<<dp[n][m]<<endl;
    }
    return 0;
}
・Q3-6. 部分和問題 (応用 2)

algo-method.com

/*
C++による「動的計画法」部分和問題とナップサック問題の解答例
Q3-6. 部分和問題 (応用 2)
https://algo-method.com/tasks/352
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,a,b;
    cin>>n>>a>>b;
    vector<int> x(n);
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    vector<vector<bool>> dp(n+1,vector<bool>(a,false));
    dp[0][0]=true;
    for(int i=0;i<n;i++){
        for(int j=0;j<a;j++){
            if(dp[i][j]==false){
                continue;
            }
            dp[i+1][j]=true;
            dp[i+1][(j+x[i])%a]=true;
        }
    }
    if(dp[n][b]){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}
・Q3-7. ボールと 2 つの箱

algo-method.com

/*
C++による「動的計画法」部分和問題とナップサック問題の解答例
Q3-7. ボールと 2 つの箱
https://algo-method.com/tasks/335
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<int> w(n);
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    int m=0;
    for(int i=0;i<n;i++){
        m+=w[i];
    }
    vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
    dp[0][0]=true;
    for(int i=0;i<n;i++){
        for(int j=0;j<m+1;j++){
            if(dp[i][j]==false){
                continue;
            }
            dp[i+1][j+w[i]]=true;
            dp[i+1][abs(j-w[i])]=true;
        }
    }
    int ans=0;
    while(dp[n][ans]==false){
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

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