2019 샤 오미 학교 수험 문제 샤 오미 대 선물

1263 단어 알고리즘
샤 오미 의 집 은 성인 사탕 가게 다.안에 싸 고 쓰기 좋 으 며 재 미 있 는 제품 이 많 습 니 다.추석 이 다가 오자 샤 오미 의 집 은 쌀가루 들 에 게 고정 금액 의 큰 선물 을 준비 하려 고 한다.주어진 금액 에 대해 서 는 이 금액 을 다른 제품 (한 제품 이 선물 에 최대 한 번 등장) 으로 조합 할 수 있 는 지 판단 해 야 한다.똑똑 한 자네 가 쌀 집 동 료 를 좀 도와 주 게.
입력 설명:
   N (N     , N  <= 200)
   N    p(   , p <= 10000)      
     M(M    ,M <= 100000 )

출력 설명:
        1
     0

예시 1
입력
6
99 199 1999 10000 39 1499
10238

출력
1

질문
사고: 모든 상품 은 선택 과 선택 하지 않 는 두 가지 상태 가 있 습 니 다.
동적 계획 dp [i] [j] 는 전 i 개 상품 이 j 로 구 성 될 수 있 는 지 여 부 를 나타 낸다.
방정식 을 dp [i] [j] = dp [i - 1] [j] | (j > = num [i] & dp [i - 1] [j - num [i]]] 로 옮 깁 니 다.
#include 
using namespace std;
const int N = 250;
const int M = 100100;
int num[N];
bool dp[N][M];

int main()
{
    int n,m;
    cin>>n;
    dp[0][0] = true;
    for(int i=1;i<=n;i++) {
        cin>>num[i];
        dp[i][0] = true;
    }
    cin>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
                 dp[i][j] = dp[i-1][j] || (j>=num[i] && dp[i-1][j-num[i]]);
        }
    }
    cout<

좋은 웹페이지 즐겨찾기