0-1背包判斷物品能否組合問題

題目描述

小米之家是成人糖果店。裡面有很多便宜，好用，好玩的産品。中秋節快到了，小米之家想給米粉們準備一些固定金額大禮包。對于給定的一個金額，需要判斷能不能用不同種産品（一種産品在禮包最多出現一次）組合出來這個金額。聰明的你來幫幫米家的小夥伴吧。

輸入描述:

輸入 N （N 是正整數， N <= 200）

輸入 N 個價格p（正整數, p <= 10000）用單空格分割

輸入金額 M（M是正整數，M <= 100000 ）

輸出描述:

能組合出來輸出 1

否則輸出 0

示例1

輸入

複制

6

99 199 1999 10000 39 1499

10238

輸出

複制

#include <iostream>
#include<vector>
using namespace std;

int main(){
    int N;
    vector<int> Input;
    int M;
    scanf("%d",&N);
    for(int i = 0;i < N;i ++){
        int tmp;
        scanf("%d",&tmp);
        Input.push_back(tmp);
    }
    scanf("%d",&M);
    vector<bool> dp(M + 1,false);
    dp[0] = true;
    for(int i = 0;i < Input.size();i ++){
        for(int j = M;j >=Input[i];j --){
            dp[j] = dp[j] || dp[j - Input[i]];
        }
    }
    if(dp[M]){
        printf("1");
    }
    else{
        printf("0");
    }
    return 0;
}