简单背包问题

发表于 | 分类于 | 阅读数
字数统计: 468 | 阅读时长 ≈ 2

背包问题

算法题目

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

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

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

输入

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

输出

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

样例输入

1
2
20 5
1 3 5 7 9

样例输出

1
YES

算法分析

这是一个典型的动态规划问题，动态规划问题需要我们想的比较抽象一点，并且他常常又与递归结合，寻找最终的结果需要我们结合问题找到根本的执行步骤，例如此题，我们可以看作我们先找到目标的部分重量，然后再看剩下的目标重量是否能够通过我们已有的重量刚刚合适。W(n)=W(n-1)+Wi;其中Wi就是我们先找到的部分重量。

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
using namespace std;
int s,n;
int flag=0;
int a[10001];
void Bag(int weight,int number)
{	
	if(weight>0&&number>=0)
	{  
	    for(int i=0;i<number;i++)
	    {
	    	Bag(weight-a[number-i],number-1);	    	 
		}
	}
	else if(weight==0)
	{
		flag=1;
	}
	else if(number==0||weight<0)
	{
		return;
	}
 
}
int main()
{
    while(cin>>s>>n)
    {
    	for(int i=0;i<n;i++)
    	{
    		cin>>a[i];
		}
	    Bag(s,n-1);
		if(flag==1)
		{
			cout<<"YES";
		}
		else
		{
			cout<<"NO"; 
		}
		cout<<endl;
		flag=0;		
	}
	return 0;
}