文章

105

粉丝

69

获赞

117

访问

54.0k

头像
小偷的背包(01背包) 题解:
P1123 中国科学技术大学机试题
发布于2024年7月14日 19:03
阅读数 333

把重量看成体积 

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int dp[N], v[N]; 
int n, s;

int main()
{
	cin >> s >> n;
	
	for(int i = 1; i <= n; i ++)
		scanf("%d", &v[i]);
	
	for(int i = 1; i <= n; i ++)
		for(int j = s; j >= v[i]; j --)
			dp[j] = max(dp[j], dp[j - v[i]] + v[i]);

	if(dp[s] == s) cout << "yes!";
	else cout << "no!";
	
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发