- 01背包问题
#include<bits/stdc++.h> using namespace std; const int mod =1000000007; //背包问题的演变(只不过是两种物品,每种物品得) vector<vector<int>> dp(1001,vector<int>(210,0)); int main(){ int k, a,x,b,y; cin>>k; cin>>a>>x>>b>>y; int length = x+y; int len[210]; for(int i = 1; i<= x;i++){ len[i] = a; } for(int i = x +1; i<=length;i++){ len[i] = b; } dp[0][0] = 1;//必要的初始条件,否则加出来永远是0 for(int j = 1;j <=length; j++){ for(int i = 0; i<=k; i++){ if(i>=len[j]){ dp[i][j] = (dp[i][j-1] + dp[i-len[j]][j-1])%mod; }else{ dp[i][j] = (dp[i][j-1])%mod; } } } cout<<dp[k][length]<<endl; return 0; }