首页 > 试题广场 >

神奇的口袋

[编程题]神奇的口袋

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

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

输入描述:

输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。

输出描述:

输出不同的选择物品的方式的数目。

示例1

输入

输出

算法知识视频讲解

Java

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));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(br.readLine());
        int[][] memory = new int[n + 1][41];
        System.out.println(recurrent(arr, 0, 40, memory));
    }
    
    private static int recurrent(int[] arr, int index, int rest, int[][] memory) {
        // 到头了
        if(index == arr.length){
            if(rest != 0)
                return 0;     // 还没凑出来
            else
                return 1;     // 凑出来了，返回一种方案
        }
        if(rest < 0){
            // 凑过头
            return 0;
        }else if(rest == 0){
            return 1;
        }else{
            // 缓存命中，直接返回
            if(memory[index][rest] != 0) return memory[index][rest];
            memory[index][rest] = recurrent(arr, index + 1, rest, memory) + recurrent(arr, index + 1, rest - arr[index], memory);
            return memory[index][rest];
        }
    }
}

发表于 2021-11-20 19:00:58 回复(0)

Java

LHC0512

Java 递归解法

import java.util.Scanner;

public class Main {
    static  int[] record ;
    static  int n ;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        record =new int[n];
        for (int i = 0; i < n; i++) {
            record[i]=scanner.nextInt();
        }
        int count = fun(0, 40);
        System.out.println(count);
    }
    static int  fun(int i,int sum){
        //结束
        if (i==n) return 0;
        //刚好够，注意，这里还可以不填充继续递归
        if (record[i]==sum) return 1+fun(i+1,sum);
        else if (sum>record[i]) return fun(i+1,sum-record[i])+fun(i+1,sum);
        //sum<record[i]
        return fun(i+1,sum);
    }
}

发表于 2020-03-06 17:22:43 回复(0)

Java

力喜

Java实现。动态规划dp。

思路：建立 (n+1)*(40+1) 的表格dp，dp[i][j]表示i中物品构成容积为j的方法数。
重点在于dp公式的推导:
若j>=items[?]，说明i种有机会构成j体积的物品，
比如，当前是第3种物品，该物品对应的体积为30，即items[?]=30,当j=35时，即需要求第3种物品构成35体积的方法数method(3,35)
而第2种物品构成体积30的方法数为1，这时就需要知道构成35-30=5的方法数，那么： method(3,35)=method(2,35-30)*第3种物品构成30体积这1种方法+method(2,35)*第3种物品构成0体积这1种方法。
因此method(3,35)=method(2,35-30)+method(2,35)，则dp[i][j]=dp[i-1][j-items[?]]+dp[i-1][j]
若j<items[?]，说明新的第i种物品不足以单个构成j体积的物品，那么dp[i][j]=dp[i-1][j]*第i种物品构成0体积这1种方法。

dp数组第一列均为1，因为第i种物品构成0的体积的方法数为1，因为后续如果遇到j=items[i-1]时
dp[i][j]=dp[i-1][j]*1(第i种物品构成0体积) +dp[i-1][0]*1(第i种物品构成j体积)
这时的dp[i-1][0]应为1，所以第一列的所有数字(包括dp[0][0])都是1。代码如下：

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] items=new int[n];
        int[][]dp=new int[n+1][41];
        for(int i=0;i<n;i++)
        {
            items[i]=in.nextInt();
        }
System.out.println(kindsOfMethods(items,dp));
    }


    //传入每个物体的体积和dp数组
public static int  kindsOfMethods(int[] items,int[][] dp)
{
    for(int i=0;i<dp.length;i++)
    {
        dp[i][0]=1;
    }
    for(int i = 1;i<dp[0].length;i++){
        dp[0][i] = 0;
    }
//遍历dp数组,为dp数组赋值
    //行
    for (int i=1;i<dp.length;i++)
        //列
    {  for(int j=1;j<dp[0].length;j++)
        {
            if(j>=items[i-1])
            {
                dp[i][j]=dp[i-1][j]+dp[i-1][j-items[i-1]];
            }
else dp[i][j]=dp[i-1][j];
        }
}
return dp[items.length][40];}



}

发表于 2020-01-25 21:07:18 回复(0)

Java

/xinCupid☆

水题一道

import java.util.*;
public class Main {
    public static void helper(int[] items, int n, int start, int[] cnt) {
        if (n == 0) {
            cnt[0]++;
            return; 
        }
        for (int i = start; i < items.length; ++i) {
            if (n >= items[i]) {
                n -= items[i];
                helper(items, n, i+1, cnt);
                n += items[i];
            }
        }
    }
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        int[] items = new int[n];
        for (int i = 0; i < n; ++i) {
            items[i] = reader.nextInt();
        }
        int[] cnt = new int[1];
        helper(items, 40, 0, cnt);
        System.out.println(cnt[0]);
    }
}

发表于 2018-06-01 10:43:31 回复(0)

Java

日进一步

import java.util.*;
public class Main {
static final int V = 40;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);

while(input.hasNext()) {
int n = input.nextInt();
int[] weight = new int[N+1];
int[] flag = new int[N+1];
//标记数组，以1代表取，0代表不去，穷举所有的可能性，总重量==S即count+1；

int count = 0;
int all_count = 1;

for(int i=1;i<=N;i++) {
weight[i] = input.nextInt();
}

for(int i=1;i<=N;i++)//计算所有可能性次数，即2的n次方
all_count *=2;

for(int num=0;num<=all_count;num++) {
for(int i=1;i<=N;i++) {//穷举所有的可能性
if(flag[i]==0) {
flag[i]=1;
continue;
}
else {
flag[i]=0;
break;
}
}
int sum = 0;//每次新方案总重量初始化为0
for(int i=1;i<=N;i++) {
if(flag[i]==1)
sum += weight[i];
}
if(sum==V)
count++;
}
System.out.println(count);
}
}

}

递归

import java.util.*;

public class 神奇的口袋递归 {
    static int[] weight;
    static int N;
    static int count=0;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);

        while (input.hasNext()) {
            N = input.nextInt();
            weight = new int[N+1];

            for (int i = 1; i <= N; i++) {
                weight[i] = input.nextInt();
            }

            beibao(40,N);
            System.out.println(count);

        }
    }
    static void beibao(int s,int n) {//s为剩余物品重量，n为剩余可选物品数
        if(s==0) {//如果正好装满
            ++count;
            return ;
        }
        if(s<0||(s>0&&n<1))//是s<0或n<1则不能完成
            return ;
        beibao(s-weight[n],n-1);//从后往前装，装上weight[n]后，若剩余物品仍然有解
        beibao(s,n-1);//若装了weight[n]后，无解，则删除该包,尝试第n-1个
    }
}

编辑于 2018-02-08 11:09:52 回复(0)