個数制限つき部分和問題 蟻本p62

問題

n種類の数aiがそれぞれmi個づつあります。
これらの中からいくつか選び，その総和をちょうどKとすることができるかを判定します。

制約

1<=n<=100
1<=ai,mi<=100000
1<=K<=100000

コード

今日はここまでの理解。

途中　|=　で論理和をとった結果で置き換えるのは+=とか-=と同じ書き方ですね。どこかで見ました。

for(int k=0;k<=m[i] && k*a[i]<=j;k++)　というfor文の条件の中に論理演算を入れてしまうのもこれまであまり経験がありませんでした。

dp[i+1][j]:＝i番目まででjを作る際に余る最大のi番目の個数（作れない場合は-1）でdpテーブルを組むことでもっと計算量を落とすことができるようですが今後の課題にします。

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

bool dp[110][100100];

int main(){
  int n;
  cin >> n;
  int a[110];
  int m[110];
  int K;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<n;i++){
    cin>>m[i];
  }  
  
  cin>>K;
  dp[0][0]=1;
  for(int i=0;i<n;i++){
    for(int j=0;j<=K;j++){
      for(int k=0;k<=m[i] && k*a[i]<=j;k++){
        dp[i+1][j] |= dp[i][j-k*a[i]];
      }
    }
  }
  cout<<dp[n][K]<<endl;
}