Coins (hdu 2844) 다중 가방
이 문제는 신키보드에 있는 댄서의 틀을 배웠습니다. 감사합니다~
이 문제는 간단한 다중배낭으로 이 동전을 완전배낭으로 할지 01배낭으로 할지 판단하고, 01배낭은 2진법으로 간소화한다.
제목은 모두 몇 가지의 price를 표시할 수 있는지 구하는 것입니다. 여기서 답안은 dp[i]==i로 판단합니다. 원인은 다음과 같습니다.
이 문제는 모두 0으로 초기화되었다. 즉, 가득 채우지 않고 최대를 구하는 것이다. 동전은 배낭 용량을 대표하는 동시에 배낭 안의 값이기도 하다.dp[i] 즉 최대 용량이 i일 때 i를 담는 것이 가장 크고 dp[i]의 값이 i와 같지 않으면 가득 채우지 못했다는 뜻이다. 즉, dp[dp[i]=dp[i]가 있기 때문에 모든 price가 dp[price]에 나타나기 때문에 이렇게 결과를 구한다.
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;
int n,m;
int v[110];
int t[110];
int dp[100010];
void MP(int value,int space,int num);
int main(){
scanf("%d%d",&n,&m);
while(n||m){
for(int i=0;i<n;i++){
scanf("%d",&v[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&t[i]);
}
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++){
MP(v[i],v[i],t[i]);
}
int sum = 0;
for(int i=1;i<=m;i++){
if(i==dp[i]) sum++;
}
printf("%d
",sum);
scanf("%d%d",&n,&m);
}
return 0;
}
//
void CP(int value,int space){
for(int i=value;i<=m;i++){
dp[i] = max(dp[i],dp[i-value] + space);
}
}
//01
void ZOP(int value,int space){
for(int i=m;i>=value;i--){
dp[i] = max(dp[i],dp[i-value] + space);
}
}
//
void MP(int value,int space,int num){
if(num*value>=m){//
CP(value,space);
}
else{//
int k=1;
while(k<=num){
ZOP(value*k,space*k);
num-=k;
k*=2;
}
ZOP(value*num,space*num);
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
