【计算思维作业】C.思维之花
题目
李老师正准备暑假旅行，他有一个容量为L的行李箱和n个物品（n不超过20），每个物品都有自己的体积，物品可以放入行李箱，但行李箱中物品的总体积不能超过行李箱容量，李老师现在想知道他有多少种携带物品的方案（一个物品都不带也算一种方案）
输入 数据第一行为两个正整数n和L，分别代表物品总数和行李箱容量，n<=20，L<=1e9 接下来一行为n个正整数vi，代表第i个物品的体积，vi<=1e8
输出数据方案数
样例输入3 10
2 4 5
样例输出7
思路
虽然题目已经提示我们这是简单背包问题，但是以我贫瘠的算法知识水平，我不会01背包的所有方案问题……
所以只能用其他方法了。
仔细 思考 一会儿，如果用枚举的思路，需要对物品求所有的组合情况，然后对每个组合求和，若和小于等于背包容量，则计数器加一。
所以难点现在变成了求所有组合。以我贫瘠的算法知识，我不会。
求助于gpt，gpt给我了一份代码，我对这份原始代码进行了加工与优化，最后把这道题AC啦。
先看看gpt辅助下我的代码吧。
回顾一下数学知识：
集合 中有n个元素
子集数： 非空子集数： 非空真子集数：
代码和解析
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
int n,l,count;
cin>>n>>l;
count=0;
vector<int> nums(n,0);
for(int i=0;i<n;i++)
cin>>nums[i];
for (int i = 0; i < (1 << n); ++i) {
std::vector<int> combination;
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) {
combination.push_back(nums[j]);
}
}
int sum = accumulate(combination.begin(), combination.end(), 0);
if(sum<=l) count++;
}
cout<<count<<endl;
return 0;
}
cpp
代码的逻辑和我在“思路”里阐释的一样，求所有组合情况的每个和，与容量比较，得到count值即为所有方案数。
核心和难点就在第二个for：详细剖析一下
1<<n：位运算，值为，也就是子集数
i：0，1，2……
j：0，1，2……n
以样例n=3为例
i：0，1，2……7，二进制就是(000,001,010,011,100,101,110,111)
j：0，1，2
1<<j：，，，，二进制就是（001,010,100）
i和1<<j进行&位运算
(000)&(001,010,110)即(i=0,j循环) 表达式全为0，combination为空，和为0，即背包没有放物品，空集的情况，count++
(001)&(001,010,100)即(i=1,j循环) 只有001&001时表达式非0，其他情况全为0，combination内只有nums[0] (j=0时1<<j==1)，combination求和==2，小于背包容量，count++
(010)&(001,010,100)即(i=1,j循环) 只有010&010时表达式非0，其他情况全为0，combination内只有nums[1] (j=1时1<<j==2)，combination求和==4，小于背包容量，count++
……
看到这里就明白了，转化为二进制后，每一位可表示成，从右往左下标从0开始增大，1<<j对应着nums[0][1][2]的数字，
（坏了感觉我的语言表达能力太拉垮了，大家看不懂就自己调试/手搓一下吧QAQ）
相关知识
【计算思维作业】C.思维之花
培育思维之树，绽放智慧之花——黄山市实验小学开展数学思维导图设计大赛
智慧之花——思维导图
最经典的思维：多米诺思维
高中心理健康 绽放思维之花 课件 (19张PPT)
曹勇军：绽放在语文课堂上的思维之花
让思维之树绽放智慧之花课堂语录
让思维之树绽放智慧之花名师
花的科普思维导图 花卉思维导图的下载方式
花知识点思维导图
原文链接: 【计算思维作业】C.思维之花 https://m.huajiangbk.com/newsview2606750.html
| 上一篇: 心叶球兰的水培方法，水深不能超过... | 下一篇: 取两个相同大小的容器，分别加入等... |
