【9405】背包问题
背包 问题
2023-09-14 09:03:46 时间
Time Limit: 10 second
Memory Limit: 2 MB
问题描述
简单的背包问题。设有一个背包,可以放入的重量为s。现有n件物品,重量分别为w1,w2.....wn(1≤i≤n),均为正整数,从n件物品中挑选若干件,使得放入背包的重量之和正好为s。找到一组解即可,如果不存在解,则输出“not found”。
Input
第一行是物品总件数和背包的载重量,第二行为各物品的重量。
Output
各所选物品的序号和重量。(定义输出物品较少的组合)
Sample Input
5 10 1 2 3 4 5
Sample Output
number:1 weight:1
number:4 weight:4
number:5 weight:5
【题解】
这是一个搜索问题。只要枚举每个物品是否在背包中即可。用sum变量来累加,如果sum > v则跳出搜索。因为要找最少物品数量,所以如果当前用掉的物品大于最小值也可以剪枝。当然你得先找到一组解,这个剪枝才有意义。
【代码】
#include <cstdio> int n,v,a[20],sum = 0,min_n = 2100000000,b[20],ans[20]; //min_n在更新一组解之后变成一个剪枝的判断符 void input_data() { scanf("%d %d",&n,&v); for (int i = 1;i <= n;i++) scanf("%d",&a[i]); } void sear_ch(int x,int num) //表示当前枚举到第x个物品,已经装了num个物品 { //可以加上一句 if num >= min_n return... if (sum > v) return; //如果超过了背包的容积则剪枝 if (sum == v) //如果恰好等于容积 则尝试更新答案。 ans是记录答案的数组,b则是动态变化的。 { if (num < min_n) { min_n = num; for (int i = 1;i <= b[0];i++) ans[i] = b[i]; } return; } if ( x > n) return; sum+=a[x]; //表示第x个物品要放进背包中 b[0]++; b[b[0]] = x; sear_ch(x+1,num+1); b[0]--; sum-=a[x]; sear_ch(x+1,num); //表示第x个物品不放进背包中。 } void get_ans() { sear_ch(1,0); } void output_ans() { if (min_n == 2100000000) //记住是“==”,输出无解信息。 { printf("not found"); return; } for (int i = 1;i <= min_n;i++) printf("number:%d weight:%d\n",ans[i],a[ans[i]]); } int main() { //freopen("F:\\rush.txt","r",stdin); input_data(); get_ans(); output_ans(); return 0; }
相关文章
- Java实现背包问题
- Python基于回溯法解决01背包问题实例
- 动态规划之背包问题
- 1050. 鸣人的影分身(计数DP,完全背包做法)
- 【动态规划】0 - 1背包问题(通俗易懂, 万能统一代码)
- LintCode 440 · 背包问题 III---完全背包问题
- LindCode 92 · 背包问题----01背包问题
- 【智能算法】模拟退火算法求解 0-1 背包问题
- 背包问题学习
- HDU 2159 FATE (完全背包+有限尚需时日)()双费背包
- 01背包问题
- 背包问题
- HDU 2159 FATE(全然背包+二维费用背包)
- 动态规划 背包问题算法模板 0-1背包 0-1带价值背包 多重背包问题
- Vijos、洛谷——采药(部分背包问题)(java实现)
- 12. 背包问题求具体方案(贪心+01背包)
- 278. 数字组合(01背包,恰好)
- 8. 二维费用的背包问题(01背包)
- 4. 多重背包问题 I(背包模型)
- Python ---- 算法入门(1)贪心算法解决部分背包问题
- 动态规划02---你的背包怎么背也背不烂~~~专治各种01背包问题