首页 > 代码库 > 百练 2755 神奇的口袋
百练 2755 神奇的口袋
第一种解法是很经典的动态规划,对于值域较小的题目,还可以采用第二种方法,考虑对值域空间-即对容积的可达性进行动态规划。
这道题里面采用第二种解法还会有空间上的优化。
有时把值域作为一种状态不单单是一种解法,还有可能是唯一的解法。如HDU 1574 RP问题
描述
有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。John现在有n个想要得到的物品,每个物品的体积分别是a1,a2……an。John可以从这些物品中选择一些,如果选出的物体的总体积是40,那么利用这个神奇的口袋,John就可以得到这些物品。现在的问题是,John有多少种不同的选择物品的方式。
输入
输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1,a2……an的值。
输出
输出不同的选择物品的方式的数目。
动规解法:
人人为我
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 int dp[45][45]; //dp[i][j]表示前j件物品总体积是i的方案总数 8 int a[45]; 9 10 int main(void)11 {12 #ifdef LOCAL13 freopen("2755in.txt", "r", stdin);14 #endif15 16 int n;17 scanf("%d", &n);18 dp[0][0] = 1;19 20 int i;21 for(i = 1; i <= n; ++i)22 {23 scanf("%d", &a[i]);24 dp[0][i] = 1;25 }26 int j;27 for(i = 1; i <= 40; ++i)28 for(j = 1; j <= n; ++j)29 {30 dp[i][j] = dp[i][j-1];31 if(a[j] <= i)32 dp[i][j] += dp[i-a[j]][j - 1];33 }34 printf("%d\n", dp[40][n]);35 return 0;36 }
我为人人
其中j从40倒着循环是考虑到,如果从1开始循环会导致重复加和的情况,从而结果错误。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 int sum[42]; //sum[i]表示到达体积i的方案总数 8 9 int main(void)10 {11 #ifdef LOCAL12 freopen("2755in.txt", "r", stdin);13 #endif14 15 int n, i, j;16 scanf("%d", &n);17 memset(sum, 0, sizeof(sum));18 while(n--)19 {20 int input;21 scanf("%d", &input);22 for(j = 40; j >= 1; --j)23 {24 if(sum[j]>0 && j+input <= 40)25 sum[j+input] += sum[j];26 }27 ++sum[input];28 }29 printf("%d\n", sum[40]);30 return 0;31 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。