文章
99
粉丝
120
获赞
8
访问
96.9k
#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;
}
}
登录后发布评论
暂无评论,来抢沙发