首页 > 试题广场 >

小米大礼包

[编程题]小米大礼包

热度指数：4757 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小米之家是成人糖果店。里面有很多便宜，好用，好玩的产品。中秋节快到了，小米之家想给米粉们准备一些固定金额大礼包。对于给定的一个金额，需要判断能不能用不同种产品（一种产品在礼包最多出现一次）组合出来这个金额。聪明的你来帮帮米家的小伙伴吧。

输入描述:

输入 N （N 是正整数， N  <= 200）
输入 N 个价格p（正整数, p <= 10000）用单空格分割
输入金额 M（M是正整数，M <= 100000 ）

输出描述:

能组合出来输出 1
否则输出 0

示例1

输入

6
99 199 1999 10000 39 1499
10238

输出

算法知识视频讲解

pein531

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null) {
            int n = Integer.parseInt(strN);
            String[] strPrice = br.readLine().trim().split(" ");
            int[] price = new int[n];
            for(int i = 0; i < n; i++) price[i] = Integer.parseInt(strPrice[i]);
            int m = Integer.parseInt(br.readLine().trim());
            System.out.println(solve(price, m));
        }
    }
    
    private static int solve(int[] price, int m) {
        int n = price.length;
        // dp[i][j]表示用0~i的物品能否凑到价值为j的礼包
        boolean[][] dp = new boolean[n][m + 1];
        // 用0~n-1的物品肯定都能凑成价值为0的礼包
        for (int i = 0; i < n; i++)
            dp[i][0] = true;
        // 仅用物品0，只能构成价值为price[0]的礼包，所以只有相等的时候为true
        for (int j = 0; j <= m; j++)
            if(price[0] == j) dp[0][j] = true;
        // 动态规划
        for(int i = 1; i < n; i++){
            for (int j = 1; j <= m; j++) {
                if(j < price[i])     // 无法选择物品i，选了就会超过价值j
                    dp[i][j] = dp[i - 1][j];
                else{
                    /*可以选择物品i，此时的状态取决于使用0~i-1的物品是否构成了
                      价值为j的礼包，如果构成了，从状态dp[i-1][j]直接转移过来,
                      本次不选择i物品。否则从dp[i][j-price[i]]转移过来，本次
                      选择物品i
                     */
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - price[i]];
                }
            }
        }
        return dp[n - 1][m] ? 1: 0;
    }
}

发表于 2020-10-25 14:19:35 回复(0)

C/C++

nbgao

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

int main(){
    int n, m, s=1;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>m;
    bool dp[m+1];
    memset(dp, false, sizeof(dp));
    dp[0] = true;
    for(int i=0;i<n;i++)
        for(int j=m;j>=a[i];j--)
            dp[j] = dp[j] || dp[j-a[i]];
    cout<<dp[m]<<endl;
    return 0;
}

发表于 2020-01-09 03:22:41 回复(0)

大厂offer呢

贴一个平民版更容易看懂的

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int target = sc.nextInt();

        boolean[][] dp = new boolean[n][target + 1];
        dp[0][0] = true;
        for (int i = 1; i <= target; i++) {
            if(arr[0] == i) {
                dp[0][i] = true;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if(j >= arr[i]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i]];
                }
            }
        }

        System.out.println(dp[n - 1][target] ? 1 : 0);
    }
}

发表于 2019-10-16 20:26:26 回复(0)

Python

秋梨膏个offer

import sys
n=int(sys.stdin.readline().strip())
price=list(map(int,sys.stdin.readline().split()))
money=int(sys.stdin.readline().strip())
res=[0 for i in range(money+1)]
res[0]=1
for num in price:
i=money
while i>=num:
res[i]=res[i]+res[i-num]
i-=1
if res[-1]>=1:
result=1
else:
result=0

print(result)

####60% leetcode 494 目标和动态规划

发表于 2019-08-31 17:26:42 回复(0)

C/C++

北雷北雷

简单暴力递归，超时

//通过65%
bool count(int sum,int currend_index) {
    if (sum == total) return true;
    else if (sum > total||currend_index>=n) return false;
    else return count(sum, currend_index + 1) || count(sum + m_array[currend_index], currend_index + 1);
}

优化为背包遍历,就可以了

#include <iostream>
#include <vector>

using namespace std;
vector m_array;
int n, total;
int main() {
    int temp;
    cin >> n;
    for (unsigned int j = 0;j < n;++j) {
        cin >> temp;
        m_array.push_back(temp);
    }
    cin >> total;
    //cout << count(0,0);
    vector result(total+1,0);
    result[0] = 1;
    for (unsigned int i = 0;i < n;++i) {
        for (unsigned int j = total;j >= m_array[i];--j) {
            result[j] = result[j] || result[j - m_array[i]];
        }
    }
    cout << result[total];
    system("pause");
    return 0;
}

编辑于 2019-07-27 16:51:12 回复(0)

C/C++

ElonB

/*
0-1背包变式，通过率低的原因应该是除了C/C++其他都超时
*/
#include <bits/stdc++.h>
using namespace std;

int main(void)
{
    int n;
    cin >> n;
    int p[n], i, j, m;
    for(i = 0; i < n; i++) cin >> p[i];
    cin >> m;
    bool ans[m + 1];
    memset(ans, 0, sizeof(ans));
    ans[0] = true;
    for(i = 0; i < n; i++) {
        for(j = m; j >= p[i]; j--) {
            ans[j] = ans[j] || ans[j - p[i]];
        }
    }
    cout << ans[m] << endl;
    return 0;
}

编辑于 2019-08-14 22:10:07 回复(2)

yan235689147

典型的0-1背包问题，状态转移方程为f[i][j]=f[i-1][j] || f[i-1][j-v[i]]，优化为一维，从右往左更新一维数组，初始化f[0]=1，因为m为0时不取任何物品就成立。

int solve(){
    vector<bool> f(m + 1);
    f[0] = 1;
    for(int i = 0; i < n; i++){
        for(int j = m; j >= v[i]; j--){
            f[j] = f[j] || f[j - v[i]];
        }
    }
    return f[m];
}

这里数组v为输入的元素，n为元素个数，m为金额，处理输入和main就不放上来了。更详细的分析请参考LeetCode 416。

发表于 2019-04-06 09:36:29 回复(0)

昀轩

python 用01背包解也过不了，就发现了这个方法。

N = int(input())
price = list(map(int, input().split(' ')))
m = int(input())

possible_sum = 1
for p in price:
    possible_sum |= (possible_sum << p)
print(possible_sum >> m & 1)

发表于 2019-09-11 09:37:28 回复(4)

牛客497864927号

动态规划，dp[i][s]表示前i个产品能否组合出金额s，则状态转移方程为dp[i][s] = dp[i-1][s] | dp[i-1][s-A[i]]。技巧: 可以只记录dp[s],节省内存空间。

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;


int main()
{
    int n, m;
    scanf("%d", &n);
    vector<int> A(n+1);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &A[i]);
    scanf("%d", &m);
    vector<bool> dp(m+1, false);
    dp[0] = true;

    int preSum = 0;
    for (int i = 1; i <= n; ++i)
    {
        preSum += A[i];
        for (int s = min(preSum, m); s >= 0; --s)
            if (s >= A[i]) dp[s] = dp[s] | dp[s-A[i]];
    }
    printf("%d\n", dp[m]?1:0);

    return 0;
}

编辑于 2021-01-04 18:59:24 回复(0)

靖笙

//回溯法  超时了，通过率只有70%
import java.util.*;
public class Main{
    static int  mark = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i<arr.length;i++){
            arr[i]=sc.nextInt();
        }
        int price = sc.nextInt();
        helper(arr,new int[n],price);
        System.out.println(mark);
    }
    public static void helper(int[] arr,int[] flag,int price){
        if(mark==1||price<0){
            return;
        }
        if(price==0){
            mark = 1;
            return;
        }
        for(int i = 0;i<arr.length;i++){
            if(flag[i]==1){
                continue;
            }       
            flag[i]=1;
            price-=arr[i];        
            helper(arr,flag,price);
            price+=arr[i];
            flag[i]=0;
        }
    }
}

编辑于 2020-07-19 19:56:02 回复(0)

LemonSky95

bitset优化01背包

#include <bits/stdc++.h>
using namespace std;
 
int p[205];
bitset<100001> dp(0);
 
int main()
{
    int n, m;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", p + i);
    scanf("%d", &m);
    dp[0] = 1;
    for (int i = 0; i < n; i++)
        dp |= dp << p[i];
    cout << dp[m] << endl;
    return 0;
}

发表于 2019-09-10 12:58:00 回复(0)

Java

崔乐颖

求讲解

发表于 2019-09-05 20:40:30 回复(0)

zjut

package 小米;

import java.util.Scanner;

public class 小米大礼包 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int N = in.nextInt();
            int save[] = new int[N];
            for(int i = 0;i < N;i++){
                save[i] = in.nextInt();
            }
            int sum = in.nextInt();

            int num[] = new int[sum+1];
            num[0] = 1;
            for(int i = 0;i < save.length;i++){
                for(int j = sum;j>=1;j--){
                    if(j>=save[i]){
                        if(num[j]==1){
                            continue;
                        }else{
                            if(num[j-save[i]]==1){
                                num[j] = 1;
                            }
                        }
                    }
                }
            }
            System.out.println(num[sum]);
        }
    }
}

发表于 2019-09-03 15:26:11 回复(0)

超越姐姐保佑我i

01背包问题。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] v = new int[n];
        for(int i = 0; i < n; i ++) {
            v[i] = sc.nextInt();
        }

        int m = sc.nextInt();
        boolean[] dp = new boolean[m + 1];
        dp[0] = true;
        for(int i = 0; i < n; i ++) {
            for(int j = m; j >= v[i]; j --) {
                dp[j] = dp[j] || dp[j - v[i]];
            }
        }

        System.out.println(dp[m] ? 1 : 0);
    }
}

发表于 2019-08-23 16:11:44 回复(0)

随缘笔试

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

const int maxn = 200 + 10;
const int maxm = 1e5 + 10;
bool dp[maxm];
int arr[maxn];
int n, m;
int ans; 

int main(int argv, char* argc[]) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
    scanf("%d", &m);

    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j > 0; --j) {
            if (arr[i - 1] <= j) dp[j] |= dp[j - arr[i - 1]];
        }
    }
    cout << dp[m] << endl;
    return 0;
}

发表于 2019-08-19 17:20:26 回复(0)

Java

不忘初心ff

import java.util.*;
public clas***ain{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }
            int sum=sc.nextInt();
            if(getResult(arr,sum)){
                System.out.println(1);
            }else{
                System.out.println(0);
            }
        }
    }
    //dp[i][j]表示arr的前i个数能否得到和j，每一个数都可以取或者不取
    public static boolean getResult(int[] arr,int sum){
        int n=arr.length;
        boolean[][] dp=new boolean[n+1][sum+1];
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            dp[i][0]=true;
        }
        for(int j=1;j<=sum;j++){
            dp[0][j]=false;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=sum;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=arr[i-1]){
                    dp[i][j]=dp[i][j]||dp[i-1][j-arr[i-1]];
                }
            }
        }
        return dp[n][sum];
    }
}

发表于 2019-05-17 09:43:01 回复(0)