[BOJ] 12865. 普通リュック-c++
https://www.acmicpc.net/problem/12865
解dp
dp[i][w]=物品1~iのみを考慮し、仮リュック容量wの場合の最大値
1.荷物iがリュックに入っていない場合、dp[i,w]=dp[i-1,w]
2.荷物iをリュックサックに入れ、現在の重量wから品物iの重量[i]を引いた後、品物を(i-1)に考慮したときの最大値dp[i-1]w-weight[i]と品物iの価値[i]の和がdp[i,w]となる.
解dp
dp[i][w]=物品1~iのみを考慮し、仮リュック容量wの場合の最大値
1.荷物iがリュックに入っていない場合、dp[i,w]=dp[i-1,w]
2.荷物iをリュックサックに入れ、現在の重量wから品物iの重量[i]を引いた後、品物を(i-1)に考慮したときの最大値dp[i-1]w-weight[i]と品物iの価値[i]の和がdp[i,w]となる.
#include <iostream>
int weight[101];
int value[101];
int dp[101][100001];
using namespace std;
int N,K;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for(int i=1;i<=N;i++){
cin>>weight[i]>>value[i];
}
for(int i=1;i<=N;i++){
for(int w=1;w<=K;w++){
if(weight[i]>w) // 물건i의 무게가 임시 배낭의 용량을 초과하면
dp[i][w]=(dp[i-1][w]);
else//물건 i를 배낭에 담지 않을 경우와 담을 경우 고려
dp[i][w]=max(dp[i-1][w],dp[i-1][w-weight[i]]+value[i]);
}
}
cout<< dp[N][K];
}
Reference
この問題について([BOJ] 12865. 普通リュック-c++), 我々は、より多くの情報をここで見つけました https://velog.io/@mopevxw/BOJ-12865.-평범한-배낭-cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol