以前是“来，帮我看看这道题！”

现在是“耶，网上有答案！”

只要思考，都能变成你大脑的东西。那么，你思考了么？

目录

题目——简单背包问题

题目描述

输入

输出

样例输入

样例输出

解题

完整代码

 相关题目

题目——简单背包问题

题目描述

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。 

问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。 

如果有满足条件的选择，则此背包有解，否则此背包问题无解。

输入

输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）

多组测试数据。

输出

对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO”

样例输入

 20 5 1 3 5 7 9

样例输出

 YES

 题目链接

解题

使用动态规划的思想，用 weight[1…n] 表示各个物件的重量，多个物件被选择后，最后加上物件 weight[m] 刚好满足总重量为 s ，那么必须满足 s – weight[m] 与前面选择的物件重量之和相等，重复这样操作的时候，s变成了 s – weight[m]，物件数量在原有的基础上减少1个，某个被选择的物件是重量weight[n]。从而我们可以利用递归判断是否满足条件：

 if(packet(s - weight[n - 1], n - 1)){   return true;  } else return packet(s,n - 1);

当然会遇到weight[m]相邻的前面一个物件不是被选择的行列，那么跳过此物件再作判断。

完整代码

 #include<iostream> using namespace std; int weight[1000]; bool packet(int s,int n){  if(s == 0) return true;  if(s < 0 ||(s > 0 && n < 1)){   return false;  }  if(packet(s - weight[n - 1], n - 1)){   return true;  }  else return packet(s,n - 1); } int main(){  int s, n;  while(cin>>s>>n){   for(int i = 0; i < n; i++){    cin>>weight[i];   }   if(packet(s,n))    cout<<"YES"<<endl;   else cout<<"NO"<<endl;  }  return 0; }

 相关题目

上一篇：算法——Coin Changing（最少硬币数）

如果看不明白某些算法，那是很正常的，少玩一会儿手机，专心理解几十分钟（对！几十分钟！当然是针对入门小白啦），就会搞明白的。并且，你还会说“原来辣么简单！”。——Lynn