NYOJ 5767 가방
2095 단어 dp
제목 설명
N 가지 아 이 템 이 하나씩 있 는데, Mkg 을 모 아 가방 에 담 을 수 있 는 지 물 어 본다.
입력
첫 번 째 줄 의 정수 T (T < = 1000) 는 데이터 그룹 수 를 측정 하고 각 조 의 첫 번 째 행위 (1 < N < = 1000), M (1 < m < = 1000) 은 두 개의 정수 이 며, 두 번 째 줄 의 정 수 는 N 가지 물품 의 품질 Gi (1000 이하) 를 나타 낸다.
출력
출력 "Y" 를 만 들 수 있 습 니 다. 그렇지 않 으 면 "N" 을 출력 할 수 있 습 니 다.
샘플 입력
2
3 5
1 2 3
3 7
1 2 3샘플 출력
Y
N<span style="font-size:18px;">#include<cstdio>
#include<cstring>
#include<iostream>
#define M 1000+10
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m,s=0,dp[M],v[M];
memset(dp,0,sizeof(dp));
scanf("%d%d",&n, &m);
for(int i=0; i<n; ++i){
scanf("%d",&v[i]);
s+=v[i];
}
if(s==m) printf("Y
");
else if(s<m) printf("N
");
else{
for(int i=0; i<n; ++i){
for(int j=m; j>=v[i]; --j){ //
dp[j]=max(dp[j], dp[j-v[i]]+v[i]); /* ， ， */
}
}
if(dp[m]==m) printf("Y
");
else printf("N
");
}
//printf("%d
",dp[m]);
}
return 0;
}</span>다른 해결 방안 (고 효율) 은 현재 점 을 기점 으로 추가 할 지, 추가 하지 않 을 지 선택 합 니 다. 검색:
<span style="font-size:12px;">#include <iostream>
#include<cstdio>
using namespace std;
int pack[1005],m;
bool ok;
void dfs(int i, int sum){
if(ok) return ;
if(i<1) return ;
if(sum==m){
ok=true;return;
}
if(sum>m) return;
dfs(i-1,sum+pack[i]);
dfs(i-1,sum);
}
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n, &m);
for(int i=1; i<=n; ++i){
scanf("%d",&pack[i]);
}
ok=false;
dfs(n,0);
if(ok)
printf("Y
");
else
printf("N
");
}
return 0;
}</span><span style="font-size: 24.5px;">
</span>이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
