文章

211

粉丝

1

获赞

1177

访问

61.7k

头像
小偷的背包 题解:
P1123 中国科学技术大学机试题
发布于2026年2月19日 09:45
阅读数 231

#include<bits/stdc++.h>
using namespace std;
int main() {	
	int dp[1005][1005] = {0};//只有 0 和 1 0 表示不可以 1 表示可以
	int w[1005];
	int s,n;
	while(cin >> s >> n){
		for(int i=1;i<=n;i++){
			cin >> w[i];
		}
		memset(dp,0,sizeof(dp));
		dp[0][0] = 1;//前 0 件物品中能拼凑出 0 重量的方案,所以为 1
		for(int i=1;i<=n;i++){
			for(int j=s;j>=0;j--){
				if(dp[i-1][j] == 1)
					dp[i][j] = 1;
				if(j - w[i] >= 0 && dp[i - 1][j - w[i]] == 1)
					dp[i][j] = 1;
			}	
		}	
		if(dp[n][s] == 1)
			cout << "yes!" << endl;
		else
			cout << "no!" << endl;
	}	
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发