枚举算法实践4

编程入门行业动态更新时间:2024-10-13 02:19:10

枚举<a href=https://www.elefans.com/category/jswz/34/1770096.html style= 算法实践4"/>

枚举算法实践4

题目描述

李老师正准备暑假旅行，他有一个容量为L的行李箱和n个物品（n不超过20），每个物品都有自己的体积，物品可以放入行李箱，但行李箱中物品的总体积不能超过行李箱容量，李老师现在想知道他有多少种携带物品的方案（一个物品都不带也算一种方案）

输入数据

第一行为两个正整数n和L，分别代表物品总数和行李箱容量，n<=20，L<=1e9
接下来一行为n个正整数vi，代表第i个物品的体积，vi<=1e8

输出数据

方案数

样例输入

3 10
2 4 5

样例输出

解题思路1 - 二叉树

对于每个物品，就有要或者不要，两种选法，所以可由此借助二叉树思想进行扩展。
扩展深度就是物品总数n，即根节点id==n。
当扩展到根节点时，进行判断，若当前容量不超过行李箱容量，则方案数+1。

代码1 - 二叉树

#include <iostream> //二叉树思想
#include <math.h>
using namespace std;
int count = 0; //方案数
int n, l;
int a[20]; //n<=20void plan(int id, int volume) //当前方案 背包已有volume重量的占用 对序号为id的物品进行选择（要或者不要）
{if (id == n) //扩展到根节点{if (volume <= l) //当前路径（方案）可行count++;return;}//对下一个物品进行选择 要或者不要plan(id + 1, volume); //不要，物品不放进去，当前容量保持不变，继续向下扩展plan(id + 1, volume + a[id]); //要，当前容量加上当前物品的体积
}
int main()
{cin >> n >> l;for (int i = 0; i < n; i++)cin >> a[i];plan(0, 0); //初始 从头开始（id=0) 背包当前放入物品重量为0cout << count << endl;system("pause");return 0;
}

解题思路2 - DFS

扩展界限：超重了
遍历之前要对物品体积进行排序。
剪枝思想：若当前物品重量加上的总重量超过了背包容量就停止扩展。因为之前有排序，再扩展后面更重的物品没有意义。

代码2 - DFS

#include <iostream>
#include <algorithm>
using namespace std;#define ll long longint n;
ll w[21];
ll m;
ll cnt;void dfs(int x, int Weight) //深度优先搜索   x：当前物品序号；  Weight：遍历到当前物品的总重量
{if (Weight > m) //超重了return;cnt++;                          //算上当前物品 count++for (int i = x + 1; i < n; i++) //对当前物品之后的每个物品遍历{if (w[i] + Weight < m) //剪枝策略dfs(i, Weight + w[i]);}
}
int main()
{cin >> n >> m;for (int i = 0; i < n; i++){cin >> w[i];}sort(w, w + n); //每个物品的重量 从小到大排序dfs(-1, 0); //进行dfs遍历cout << cnt;system("pause");return 0;
}