小偷的背包 题解：题目和简单背包问题一样的 为什么这边错误50%
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main(){
int weight=0,n,temp;
while(cin>>weight>>n){
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n,cmp);
for(int i=0;i<n&&weight>0;){
if(weight-a[i]>=0)weight-=a[i];
else i++;
}
if(weight==0){
cout<<"yes!"<<endl;
}
else cout<<"no!"<<endl;
}
}
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
这个是经典的动态规划背包问题，贪心算法只能通过一部分的数据。
具体可以看书上8.5背包类问题