文章

149

粉丝

0

获赞

481

访问

21.4k

头像
简单背包问题 题解:
P1035
发布于2026年3月7日 20:02
阅读数 45

#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) //如果前 i-1 个物品能凑出重量 j
					dp[i][j] = 1; //那么前 i 个物品也一定能凑出重量 j(不选第 i 个物品)
				if(j - w[i] >= 0 && dp[i - 1][j - w[i]] == 1) //如果前 i-1 个物品能凑出重量 j-w[i]
					//条件j - w[i] >= 0 要凑的重量 j 必须大于等于第 i 个物品的重量 w[i]
					//如果要选第 i 个物品,重量 j 至少要能容纳这个物品
                    //如果 j < w[i],即使想选也选不了,因为会超重
					dp[i][j] = 1; //那么选上第 i 个物品后,就能凑出重量 j
			}	
		}	
		if(dp[n][s] == 1)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}	
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发