항 저 우 전기 2602-01 배낭
8546 단어 항주 전기
http://acm.hdu.edu.cn/showproblem.php?pid=2602
문제 설명
몇 년 전,테 디 의 고향 에'뼈 줍 는 사람'이라는 사람 이 있 었 다.이 사람 은 서로 다른 뼈 를 수집 하 는 것 을 좋아 합 니 다.예 를 들 어 개,소,그 는 무덤 에 갔습니다.뼈 수집 기 는 큰 봉지 의 부피 V 가 있 고 방문 하여 많은 뼈 를 수집 하 는 것 이 뚜렷 합 니 다.서로 다른 뼈 는 서로 다른 가치 와 부피 가 있 습 니 다.지금 은 모든 뼈의 가치 와 그의 여행 을 고려 하여 가장 큰 총 가치 뼈 수집 기 는 무엇 을 얻 을 수 있 습 니까?
입력
첫 줄 은 정수 T 를 포함한다.그 다음은 T 의 경우 각 상황 에서 세 줄,첫 줄 은 두 개의 정수 N,V,V(N<=1000,<=1000)를 포함 하여 뼈의 수량 과 그의 가방 의 부 피 를 대표 한다.두 번 째 줄 에 N 개의 정 수 를 포함 하 는 것 은 모든 뼈의 가 치 를 나타 낸다.세 번 째 줄 은 N 개의 정 수 를 포함 하여 모든 뼈의 부 피 를 대표 한다.
출력
각 줄 의 정 수 는 가장 큰 총 가 치 를 대표 한다(이 숫자 는 231 보다 낮 을 것 이다).
샘플 입력
1 5 10 1 2 3 4 5 5 4 3 2 1
샘플 출력
14
01 가방 의 사상 참조:http://www.cnblogs.com/tanky_woo/archive/2010/07/31/1789621.html
코드 1:
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
int back(int *w,int *v,int n,int m);
int f[1009][1009];//
int main(){
int w[1009];//
int v[1009];//
int i,j,T,n,m;//n ,m
while(scanf("%d",&T)!=EOF){
while(T--){
memset(w,0,sizeof(w));
memset(v,0,sizeof(v));
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
}
for(i=1;i<=n;i++){
scanf("%d",&v[i]);
}
int max = back(w,v,n,m);
printf("%d
",max);
}
}
return 0;
}
int back(int *w,int *v,int n,int m){
memset(f,0,sizeof(f));
int i,j;
for(i=1;i<=n;i++){// 0 , i-1 1
for(j=0;j<=min(v[i]-1,m);j++) f[i][j]=f[i-1][j];
for(j=v[i];j<=m;j++){// 0 , j-v[i], v[i]
f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]); //(f[i-1][j]>f[i-1][j-v[i]]+w[i])?f[i-1][j]:(f[i-1][j-v[i]]+w[i]);
// cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<" ";
}
// cout<<endl;
}
/* , , , , */
return f[n][m];
return 0;
}
/* 1 5 10 1 2 3 4 5 5 4 3 2 1 f[1][5]=1 f[1][6]=1 f[1][7]=1 f[1][8]=1 f[1][9]=1 f[1][10]=1 f[2][4]=2 f[2][5]=2 f[2][6]=2 f[2][7]=2 f[2][8]=2 f[2][9]=3 f[2][10]=3 f[3][3]=3 f[3][4]=3 f[3][5]=3 f[3][6]=3 f[3][7]=5 f[3][8]=5 f[3][9]=5 f[3][10]=5 f[4][2]=4 f[4][3]=4 f[4][4]=4 f[4][5]=7 f[4][6]=7 f[4][7]=7 f[4][8]=7 f[4][9]=9 f[4][10]=9 f[5][1]=5 f[5][2]=5 f[5][3]=9 f[5][4]=9 f[5][5]=9 f[5][6]=12 f[5][7]=12 f[5][8]=12 f[5][9]=12 f[5][10]=14 14 5 5 10 1 2 3 4 5 0 0 0 0 0 5 10 1 2 3 4 5 0 0 1 0 0 5 0 1 2 3 4 5 0 0 1 0 0 5 3 1 2 3 4 5 0 0 1 2 3 5 10 1 2 3 4 5 5 5 5 5 5 3 5 6 5 4 1 5 4 3 5 2 3 3 1 8 9 */
코드 2:
# include <iostream>
# include <cstdio>
# include <algorithm>
# include <cstring>
using namespace std;
int back(int w[],int v[],int n,int m);
int f[1009];
int main(){
int n,m,T;
int i,j,k;
int v[1009];//v
int w[1009];//w
while(scanf("%d",&T)!=EOF){
while(T--){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%d",&w[i]);
for(i=1;i<=n;i++) scanf("%d",&v[i]);
int max_ = back(w,v,n,m);
printf("%d
",max_);
}
}
return 0;
}
int back(int w[],int v[],int n,int m){
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)// , for(int j=m;j>=0;j--)
f[j] = max(f[j],f[j-v[i]]+w[i]);// f[j] f[j-v[i]]+w[i]
return f[m];
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
원탁 문제 HDU 4841 PE...원탁 문제 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 466 Ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.