问题描述

有一个神奇的口袋,总的容积是40,用这个口袋可以变出
一些物品,这些物品的总体积必须是40。  John现在有n(1≤n ≤ 20)个想要得到的物品,每个物品
的体积分别是a1,a2……an。John可以从这些物品中选择一
些,如果选出的物体的总体积是40,那么利用这个神奇的
口袋,John就可以得到这些物品。现在的问题是,John有
多少种不同的选择物品的方式。
输入
输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的
数目。接下来的n行,每行有一个1到40之间的正整数,分别
给出a1,a2……an的值。

输出

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

输入样例

3
20
20
20

输出样例

3

枚举的解法:

枚举每个物品是选还是不选,共2
20种情况

显然是不可以的。
递归解法
#include <iostream> using namespace std; int a[30]; int N; int Ways(int w ,int
k) { // 从前k种物品中选择一些,凑成体积w的做法 数目 if( w == 0 ) return 1; if( k <= 0 ) return 0;
return Ways(w, k -1 ) + Ways(w - a[k], k -1 ); } int main() { cin >> N; for( int
i= 1;i <= N; ++ i ) cin >> a[i]; cout << Ways(40,N); return 0; }
动规解法
#include <iostream> using namespace std; int a[30]; int N; int Ways[50][40];
//Ways[i][j]表示从前j种物品里凑出体积i的方法数 int main() { cin >> N; memset(Ways,0,sizeof(Ways)
); for( int i = 1;i <= N; ++ i ) { cin >> a[i]; Ways[0][i] = 1; } Ways[0][0] = 1
; for( int w = 1 ; w <= 40; ++ w ) { for( int k = 1; k <= N; ++ k ) { Ways[w][k]
= Ways[w][k-1]; if( w-a[k] >= 0) Ways[w][k] += Ways[w-a[k]][k-1]; } } cout <<
Ways[40][N]; return 0; }

技术
©2019-2020 Toolsou All rights reserved,
LinkedHashMap基本用法&使用实现简单缓存 dedecms网站被黑 劫持到其他网站如何解决苹果不送充填器耳机真为环保?可能还是为了赚钱吧图片格式转换错误总结-myBatis plus 分页numpy:多维数组的创建用C语言做很简单的飞机游戏Keras保存与加载模型(JSON+HDF5)福布斯中国汽车富豪榜:何小鹏第11 李想第14 李斌第15hive大量小文件处理方法总结