【计算思维作业】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://www.huajiangbk.com/newsview2606750.html