首页 > 试题广场 >

神奇的口袋

[编程题]神奇的口袋
  • 热度指数:18496 时间限制: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

输入

3
20
20
20

输出

3
记忆化搜索,其实就跟动态规划一样的时空复杂度,可以根据递归中的依赖关系改写成动态规划
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)
使用递归方案求解:
#include<iostream>
using namespace std;
int count=0;
int n;
void dp(int a[],int p,int num)
{
    if(num==0)
    {
        count++;return;
    }
    for(int i=p;i<n;i++)
    {
        if(a[i]<=num)
            dp(a,i+1,num-a[i]);
    }
}
int main()
{
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    dp(a,0,40);
    cout<<count<<endl;
    return 0;
}


发表于 2020-04-18 12:22:51 回复(0)
#include <iostream>
#include <memory.h>

using namespace std;

int count;
int st2[40];
int n;

void depth(int sum,int position){
	if(sum>40)
		return;
	if(sum==40){
		count++;
		return;
	}

	for(int i=position;i<n;i++)
		depth(sum+st2[i],i+1);
}

int main(){
	while(cin>>n){
		for(int i=0;i<n;i++)
			cin>>st2[i];
		count=0;
		depth(0,0);
		cout<<count<<endl;
	}
	return 0;
}

发表于 2020-01-20 10:18:45 回复(1)
def findCountsNum(tempSum,nowIndex):   #通过当前的下标和前面加的数字和进行查找
    if nowIndex >= num:
        return
    if tempSum + digitNums[nowIndex] == 40:
        global count
        count += 1
        findCountsNum(tempSum,nowIndex+1)
    elif tempSum+digitNums[nowIndex] < 40:
        findCountsNum(tempSum+digitNums[nowIndex],nowIndex+1)
        findCountsNum(tempSum,nowIndex+1)


while True:
    try:
        num = int(input())
        digitNums = []
        for i in range(num):
            digitNums.append(int(input()))
        digitNums.sort()
        count = 0
        findCountsNum(0,0)
        print(count)
    except Exception:
        break
编辑于 2018-10-01 23:05:27 回复(0)
//动态规划
//具体思想:对于数字dp[i][j],i代表编历到第i个有序数,总重量为j的方式数目
//dp[i][j]的值只可能来自两个,一是继承自dp[i-1][j],此时是代表第i个有序数没有用到
//二是由dp[i-1][j-q[i]],q[i]代表第i个有序数,此时是用到了第i个有序数
//注意实现方式,我设-1为不可达,需要判断以上两种情况,加成需要判断四种情况
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> Q;
        for(int i=0;i<n;i++)
        {
            int tmp;
            cin>>tmp;
            if(tmp<=40&&tmp>0)   //读数,筛选出小于等于40的值
                Q.push_back(tmp);
        }
        int m=Q.size();
        sort(Q.begin(),Q.end());  //排序
        int dp[m+1][41];  //动态规划数组
        for(int i=0;i<41;i++)
            dp[0][i]=-1;  // 0个物品只有0可达,其余不可达。
        dp[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            int tmp=Q[i-1];
            for(int j=0;j<41;j++)
            {
                if(j-tmp<0)  //j小于tmp的只能继承自dp[i-1][j];
                {
                    dp[i][j]=dp[i-1][j];
                }
                else
                {
                    if(dp[i-1][j]==-1&&dp[i-1][j-tmp]==-1)  //四种情况,两个数值的存在不存在
                        dp[i][j]=-1;
                    else if(dp[i-1][j]!=-1&&dp[i-1][j-tmp]==-1)
                        dp[i][j]=dp[i-1][j];
                    else if(dp[i-1][j]==-1&&dp[i-1][j-tmp]!=-1)
                        dp[i][j]=dp[i-1][j-tmp];
                    else
                        dp[i][j]=dp[i-1][j]+dp[i-1][j-tmp];
                }
            }
        }
        if(dp[m][40]==-1) cout<<"0"<<endl; //不存在输出0
        else cout<<dp[m][40]<<endl;  //存在输出
    }
}

发表于 2018-03-25 10:06:38 回复(0)
#include<stdio.h>
#include<string.h>
int main(){
    int target[41], i, j, volume[20], n;
    while(scanf("%d", &n) != EOF){
        for(i=0; i<n ; ++i)
            scanf("%d", &volume[i]);
        memset(target, 0, sizeof(int)*41);
        target[0] = 1;
        for(i=0 ; i<n ; ++i)
            for(j=40; j>=volume[i] ; --j)
                target[j] = target[j] + target[j-volume[i]];
        printf("%d\n", target[40]);
    }
    return 0;
}

编辑于 2018-02-15 00:40:56 回复(0)
法一 :递归  把物品数目n和物品体积数组a[100]设为全局变量; 
count(i,sum)表示从数组的第i个数开始往后统计的组合数和为sum的种类数,
sum为组合数的和,则:cout(i,sum)=cout(i+1,sum-a[i])+cout(i+1,sum),
其中cout(i+1,sum-a[i])表示包含了a[i],即为从第i+1个数开始往后统计
组合数的和为sum-a[i]种类数, 而cout(i+1,sum)表示不包含a[i], 即为从第i+1个数开始往后统计组合数的和为sum种类数 ***********************************
#include<iostream>
using namespace std;
    
int a[100];
int n=1;
int count(int i,int sum)
{
    if(sum==0){return 1;} //找到一组和为sum的组合数;
    if(i==n||sum<0) return 0;//i==n说明没有其他的数来组合,sum<0说明组合不出;
    return count(i+1,sum-a[i])+count(i+1,sum);//从数组的第i为开始,包含a[i],和不包含;
}

int main()
{
    while(cin>>n){
    for(int i=0;i<n;i++)
      cin>>a[i];
    cout<<count(0,40)<<endl;
    }
    return 0;
} 
法二:动态规划
 #include<iostream>
using namespace std;
#define N 100
int n,a[N]; 
int main()
{
    while(cin>>n){
    int (*dp)[50]=new int[N][50];//dp[i][j]表示从前i个物品中凑出体积j;
    for(int i=1;i<=n;i++)
    {
      cin>>a[i];
      dp[i][0]=1; //初始边界
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=40;j++)
      {
        dp[i][j]=dp[i-1][j];
        if(a[i]<=j)
          dp[i][j]+=dp[i-1][j-a[i]];
      }
    cout<<dp[n][40]<<endl;
    delete []dp;
    }
    return 0;
} 
******************************************************************
***************************************************************** 法三:动态规划,对值域空间-即对容积的可达性进行动态 规划。定义一维数组 int dp[N];
依次放入物品,计算每次放入物品可达的容积, 并在相应空间设置记录,最后判断dp[40] 是否可达 ,到达了几次
#include<iostream> using namespace std; #define N 100 int n,a; int main() { while(cin>>n){ int *dp=new int[N];//dp[j]表示凑出体积i的次数; for(int i=1;i<=n;i++) { cin>>a; for(int j=40;j>=1;j--) //逆序,不然重复更新 if(dp[j]>0&&j+a<=40) dp[j+a]+=dp[j];//如果j有dp[j]种方式可达,则每种方式加上a就可达j+a dp[a]++; } cout<<dp[40]<<endl; delete []dp; } return 0; }

编辑于 2016-09-08 23:14:49 回复(4)
本题采用递归思想:
①物品n个,物品体积逐一放入a[100]中
②递归函数count(i,sum)=count(i+1,sum-a[i])+count(i+1,sum); 
其中,i为第i个物品,sum代表剩余空缺体积数 
count(i+1,sum-a[i]) 代表从第i+1个物品开始,剩余体积数为sum-a[i]的方案数
(隐含:已经将a[i]的体积计算进去,即包含a[i]的体积)  
count(i+1,sum) 代表从第i+1个物品开始,剩余体积数为sum的方案数 
(隐含:不将a[i]的体积计算进去,即不包含a[i]的体积) 
 
代码如下:
#include<stdio.h>

int a[100];
int n=1;

int count(int i,int sum){   //递归函数
    if(sum==0) return 1;
    if(i==n||sum<0) return 0;
    return count(i+1,sum-a[i])+count(i+1,sum);
}
int main(){
  while(scanf("%d",&n)!=EOF){
     for(int i=0;i<n;i++)   scanf("%d",&a[i]);
     printf("%d",count(0,40));
  }
  return 0;
}



编辑于 2018-03-07 11:33:58 回复(5)
/*dp[i]指口袋体积为i时,共有几种方法
  对于所有物品进行遍历,该物体体积为volume[i]
*/
//用滚动数组法,每次状态转移仅仅根据前一行数组决定,故选择用一维数组
#include<cstdio>
int volume[21];
int dp[41];

int main()                                
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        for (int i = 1; i<=n; i++)        //输入物品的体积
            scanf("%d", &volume[i]);
        for(int i = 1; i<=n; i++)    //对于所有物品进行遍历,该物体体积为volume[i]
        {
            for(int j = 40; j>=volume[i]; j--)    //j>=volume[i]因为dp[j]只能从0~40-volume[i]的状态转移而来
            {
                dp[j] += dp[j-volume[i]]; //如果dp[j]已经有了x种方法,而dp[j-volume[i]]也有y种方法
            }                   //那么由于物体i的存在,对于体积为j的口袋,又能多出dp[j-volume[i]]种方法
            //例如j=20,volume=10,而有5种方法能装满体积为10的口袋,那么只要有体积为10的物体就一定多出5种装满体积为20的口袋的方法
            dp[volume[i]]++;//显而易见,当口袋体积等于该物体体积时,必然有一种方法
        }             //而可能不止一个物体有这样的体积,所以每次碰到这个体积的物体,就做一次++运算
        printf("%d\n",dp[40]);
    }//while
    return 0;
}



发表于 2018-02-19 23:15:31 回复(1)
#include <stdio.h>
#define N 801

int main()
{
    int a, n;
    int method[N];//method[i]表示i有几种凑法
    while(scanf("%d", &n)!=EOF)
    {
        for(int i=0; i<N; i++)
        {
            method[i]=0;
        }
        method[0]=1;
        for(int i=0; i<n; i++)
        {
            scanf("%d", &a);
            for(int j=N-1; j>=a; j--)
            {
                method[j]+=method[j-a];
            }
        }
        printf("%d\n", method[40]);
    }
    return 0;
}
发表于 2018-02-22 12:20:02 回复(3)
#include<iostream>
using namespace std;
//方法一:递归
int count(int n, int*& a, int i, int sum)
{
	if (sum == 0)
		return 1; //找到一组和为sum的组合数;
	if (i == n || sum < 0)
		return 0;//i==n说明没有其他的数来组合,sum<0说明组合不出;
	//从数组的第i为开始,包含a[i],和不包含a[i];
	return count(n, a, i + 1, sum - a[i]) + count(n, a, i + 1, sum);
}
void recursion(int n)//递归
{
	int* a = new int[n];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cout << count(n, a, 0, 40) << endl;
	delete[] a;
}
//法二:动态规划,对物品组成的体积进行动态规划。
void dynamic(int n)
{
	int* a = new int[n + 1];
	int(*dp)[41] = new int[n + 1][41];//dp[i][j]表示从前i个物品中凑出体积j;
	for (int i = 0; i < 41; i++)
		dp[0][i] = 0;//初始边界:从前0个里凑不出任何体积
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		dp[i][0] = 1; //初始边界:随便从前几个都能凑出0体积
	}
	dp[0][0] = 1;//初始边界:0可以凑出0
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= 40; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (a[i] <= j)
				dp[i][j] += dp[i - 1][j - a[i]];
		}
	cout << dp[n][40] << endl;
	delete[] a, dp;
}
//法三:动态规划,对容积的可达性进行动态规划。
void dynamic_2(int n)
{
	int a;
	int* dp = new int[41];//dp[i]表示凑出体积i的次数;
	for (int i = 1; i <= 40; i++)
		dp[i] = 0;//初始边界:开始所有体积都没被凑出
	for (int i = 1; i <= n; i++)
	{
		cin >> a;
		for (int j = 40; j >= 1; j--) //逆序,否则要重复更新
			if (dp[j] > 0 && j + a <= 40)
				dp[j + a] += dp[j];//如果j有dp[j]种方式可达,则每种方式加上a就可达j+a
		dp[a]++;
	}
	cout << dp[40] << endl;
	delete[] dp;
}
int main()
{
	int n;
	while (cin >> n)
	{
		//recursion(n);
		//dynamic(n);
		dynamic_2(n);
	}
	return 0;
}

高赞回答动态规划时少赋了初值,修改一下
编辑于 2020-06-20 12:44:07 回复(0)
啥头像
动态规划
保存一个ways数组,ways[i]表示物品组成总重为i的方式数
对于一个重量为weight的物品,从num=40-weight开始直到0开始更新ways
更新公式为ways[num+weight] += ways[num]

最后除数ways[40]即可

#!/usr/bin/python
#-*- coding:utf-8 -*-

#Author: Ben

while True:
    try:
        N = input()
        ways = [0]*41
        ways[0] = 1
        for i in range(N):
            weight = input()
            num = 40 - weight
            while num >= 0:
                if ways[num]:
                    ways[num+weight] += ways[num]
                num -= 1
        print ways[40]
    except:
        break 


发表于 2016-04-15 10:09:12 回复(1)
#include <bits/stdc++.h>
/*
    深度搜索,我们如果找到一个解,那么直接种类加一,返回
*/
using namespace std;
const int MAXN = 25;
const int total = 40; // 总重量
bool visit[MAXN]; // 标记数组
int matter[MAXN]; // 存放物品
int kind = 0; // 记录一共有多少种
int n; // 物品的数量

void DFS(int sum,int position) { // sum为当前已经凑的质量
	if(sum==total) {
		kind++; // 种数增加
		return;
	}
	// 从第一件开始凑数
	for(int i=position; i<n; i++) {
		if(visit[i] || sum+matter[i]>total) {
			continue;
		}
		visit[i] = true;
		DFS(sum+matter[i],i);
		visit[i] = false; // 回溯
	}
}

int main() {
	cin>>n;
	int sum = 0; // 记录所有物品的质量总和
	for(int i=0; i<n; i++) {
		cin>>matter[i];
		sum+=matter[i];
	}
	sort(matter,matter+n);
	// 总和小于40或者最大的已经大于40了
	if(sum<40 || matter[0]>40) {
		cout<<kind<<endl;
		return 0;
	} else {
		memset(visit,false,sizeof(visit));
		DFS(0,0);
		cout<<kind<<endl;
	}
	return 0;
}

编辑于 2020-03-11 13:17:19 回复(1)
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define N 100
inta[N],n;
int ways(int n,int w)
{
if(w==0) return 1;
if(n<=0) return 0;
return ways(n-1,w)+ways(n-1,w-a[n]);
}
int main()
{
cin>>n;
for(inti=1;i<=n;i++)
cin>>a[i];
cout<<ways(n,40)<<endl;
return0;
}

编辑于 2016-08-20 19:26:38 回复(2)
动态规划法:
dp[i][j]表示当有i个物品时,凑成体积为j的方法数
对于第i个物品,只有拿和不拿两种选择。所以它的方法数等于拿+不拿的方法总数
dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i]]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int dp[21][41];  //dp[i][j]表示当有i个物品时,凑成体积为j的方法数
int v[21];  //体积

int main(){
    int n;
    while(cin>>n){
        for(int i=1; i<=n; i++){
            cin>>v[i];
        }
        memset(dp, 0, sizeof(dp));
        for(int i=0; i<=n; i++){
            dp[i][0] = 1; //当目标体积为0时,只有1种方法就是全不拿
        }
        
        for(int i=1; i<=n; i++){
            for(int j=1; j<=40; j++){
                if(j>=v[i]){//目标体积大于当前物品体积
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i]];//不拿+拿的方法数
                }
                else{
                    dp[i][j] = dp[i-1][j];//只能选择不拿
                }
                
            }
        }
        cout<<dp[n][40]<<endl;
    }
    return 0;
}


发表于 2020-06-26 16:48:33 回复(0)
import java.util.Scanner;

public class Main1 {
    static int count=0;//表示有多少种
    static int[] arr; //表示口袋
    static int n;//表示物品的种类
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            n=input.nextInt();
            arr=new int[n+1];
            /*这里的大小我们设置的比物品的种类要大1,因为在下边进行递归的时候,
            如果大小为n,因为在放第一个的时候还要考虑第一个的前一个(倒着放的:相对正着放方便一点),
            数组大小为n的话会造成数组溢出
             */
            for(int i=1;i<=n;i++){
                arr[i]=input.nextInt();
            }
        }
        count(40,n);
        System.out.println(count);
    }
    public static void count(int s,int n){
        /**
         * s表示背包剩下的容量大小
         * n表示剩下的东西数量
         */
        //如果背包容量刚好等于零,说明刚好装满
        if(s==0){
            count++;
        }
        //背包容量小于零或者容量大于零但是东西数量小于零,则不能刚好装满(也就是要么装不下了要么不够装了)
        if(s<=0||(s>0&&n<0)){
            return ;
        }
        //从最后一个开始装
        count(s-arr[n],n-1);
        //如果最后一个和其他是都值完了,从倒数第二个开始
        count(s,n-1);
    }
}
————————————————
版权声明:本文为CSDN博主「峰回路转」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_44840148/article/details/104704883

发表于 2020-03-06 22:03:39 回复(0)
//直接使用动态规划!
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int dp[1000][1000];
int main()
{
    int n;
    int a[30];
    scanf("%d",&n);
    int i,j;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    //应该是动态规划
    //dp[0][0]=1;
    for(j=1;j<=40;j++)
    {
       dp[0][j]=0;  //用前面0个去拼凑j体积!!就是没有方案!
    }
    for(i=0;i<=n;i++)
    {
        dp[i][0]=1;  //用前面i个去拼凑0体积的东西,就是只有一种方案!那就是什么都不取!
    }
    for(i=1;i<=n;i++)
    {   
        for(j=0;j<=40;j++)
        {
                 if(a[i]>j)
                    dp[i][j]=dp[i-1][j];
                 else if(a[i]<=j)
                 {
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
                 }
        }
    }
    printf("%d",dp[n][40]);
    return 0;
}
发表于 2018-09-07 23:08:48 回复(1)
大佬们都用动态规划,原谅我用的是暴力搜索,因为我简单算了下百万级别的能接受就想到动态规划 了
#include <bits/stdc++.h>
using namespace std;
int w[20];
int n;
int sz;
int main()
{
    //freopen("in.txt", "r", stdin);
    while (cin >> n) {
        sz = 0;
        while (n--) {
            int t;
            cin >> t;
            if (t > 40) continue;//大于40的重量直接丢弃
            w[sz++] = t;
        }
        int bin = 0;
        int cnt = 0;
        while(bin<pow(2,sz)){//一共2的sz次方种可能
            int sum = 0;
            int tmp = bin;
            for (int i = 0; i < sz; i++) {
                sum += w[i] * (tmp & 1);
                tmp = tmp >> 1;
            }
            if (sum == 40)cnt++;
            bin++;
        }
        cout << cnt << endl;
    }
    return 0;
}



编辑于 2018-07-07 22:02:24 回复(1)

python解法:使用dfs来做的。

def dfs(arr,vol):
    global res
    if vol<0:
        return
    if vol==0:
        res+=1
        return
    for i,v in enumerate(arr):
        dfs(arr[i+1:],vol-v)
while True:
    try:
        a, arr = int(input()), []
        for i in range(a):
            arr.append(int(input()))
        res=0
        dfs(arr,40)
        print(res)
    except:
        break

不过这种解法对于这道题来说是可以的,因为给的数量比较小。如果是比较大的数组就GG了。DP才是正路子啊

编辑于 2017-10-17 10:18:28 回复(0)
#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 21;

int v[maxn];        // 存储每个物品体积
int bite[maxn];     // 用于标记这个物品是否出现在最后的队列中

int count = 0;      // 计数器
int total = 0;      // 物品总数量

/**
    num : 现在要放第几个物品, num >= 0
    n : 剩余容积
*/
void solve(int num, int n)
{
    if(n == 0)
    {
        // 没有剩余容积则是一种方法
        ++count;
        return ;
    }

    if(num == total)
    {
        // 放到最后也没有结束
        return ;
    }

    bite[num] = 1;
    solve(num+1, n-v[num]);
    bite[num] = 0;
    solve(num+1, n);

}

int main()
{
    
    cin >> total;
    for(int i = 0; i < total; ++i)
    {
        cin >> v[i];
    }

    solve(0, 40);

    cout << count ;

    return 0;
}


发表于 2016-08-09 17:17:32 回复(0)