ALGORITHM NOTE 上司のおごり典型的な動的計画法の問題です。 K[i] を i 番目の金額、 Ti[j] を i 番目までの金額を使って j を払えるかのフラグとする （1の場合に払えるものとする）と、 T0[j] を 0 で初期化し、 Ti[j] = Ti-1[j] | Ti-1[j - K[i]] となります。 あとは、i が素数で T[i] が 1 である i の最大値を求めます。 #include<iostream> using namespace std; #define KMAX 30 #define VMAX 1000000 int K[KMAX], T[VMAX+1]; void eratos ( int n, bool prime[]){ for ( int i = 0; i <= n; i++ ) prime[i] = false; for ( int i = 3; i <= n; i += 2 )
