완전 배낭 도로 승차 문제
1337 단어 problem
Description
특별한 일방통행로는 킬로미터마다 정류장이 있다.고객은 그들이 차를 탄 킬로미터에 따라 비용을 지불한다.예를 들어 다음 표는 비용의 명세서이다.10킬로미터를 넘는 차는 한 대도 없고 한 고객은 n킬로미터(1<=n<=100)를 주행할 계획이다. 무한정 차를 갈아타면 여정을 마칠 수 있다.마지막으로 비용이 가장 적게 요구된다.
Input
첫 번째 줄의 10개의 정수는 각각 1~10킬로미터를 걷는 비용을 나타낸다(<=500).10킬로미터를 주행하는 것이 1킬로미터를 주행하는 것보다 비용이 적을 수 있으니 주의해라.
두 번째 줄의 정수 n은 여행객의 총 노정수를 나타낸다.
Output
최소한의 비용을 표시하는 정수만 있다.
Samples
input:
12 21 31 40 49 58 69 79 90 101
15
output:
147
다음은 제 코드입니다(처음 배낭을 배웠는데 오류가 있으면 지적해 주셔서 대단히 감사합니다).
#include
#include
#include
using namespace std;
int main(){
int n;
int cost[11];
int dp[500];
memset(dp,999999,sizeof(dp)); // dp
dp[0] = 0; // 0 0；
for(int i = 1; i <= 10; i++){
cin>>cost[i]; //
}
cin>>n; //
for(int i = 1; i <= 10; i++){ // i
for(int j = i; j <= 100; j++){
dp[j] = min(dp[j], dp[j - i] + cost[i]); // j ， ,
} // dp[j] ； ，
} // i ，
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 파트 3 : 스택을 사용하여 문자열 반전얘들 아. 오늘은 스택을 사용하여 문자열을 뒤집는 방법을 보여드리겠습니다. 이 문제에서 우리는 하나의 문자열을 받았고 스택을 사용하여 그것을 뒤집어야 합니다. 해결책 이것이 도움이 되길 바랍니다. 감사합니다 ❤....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
