文章

99

粉丝

120

获赞

8

访问

96.9k

头像
简单背包问题
综合
发布于2024年3月24日 16:12
阅读数 1.1k

#include<iostream>
using namespace std;

int main()
{
	int dp[1005][1005] = { 0 };//表示前i件物品是否能凑出重量为j的方案,0表示否,1表示是
	int w[1005];//单个物品的重量
	int s, n;//重量,件数
	while (cin >> s >> n)
	{
		int i, j;
		for (i = 1;i <= n;i++)
		{
			cin >> w[i];
		}
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for (int i = 1;i <= n;i++)
		{
			for (j = s;j >= 0;j--)
			{
				if (dp[i - 1][j] == 1)dp[i][j] = 1;
				if (j >= w[i] && dp[i - 1][j - w[i]] == 1)dp[i][j] = 1;
			}
		}
		if (dp[n][s] == 1)cout << "yes!" << endl;
		else cout << "no!" << endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发