恥ずかしい質問
6776 ワード
KnapSack問題のタイプ
色
どれも価値と重さがあり、この値に基づいてリュックサックに入れ、価値が最も高い場合を見つけます.
いろいろ
これはBret-Forceで解決する方法です.ただ2^n時間の複雑さがあり,このような解はないかもしれない.
価値の高い先放
これはグリディのやり方で解いたのです.ただ、常に最良の結果を保証することはできません.
このようにしてFractional Knapsackと呼ばれるものを切り取って入れる問題を解決することができる.
質問する
4 7
6 13
4 8
3 6
5 12
問題のリュックサックには虹を7個支えるバッグと4個のアイテムがある.このとき、dpは以下のように定義される.
dp[i][j]=最初からi番目のアイテムを表示し、リュックの容量がjの場合、リュックの最大値の和に入る.
完全なコード
#include <iostream>
#include <algorithm>
using namespace std;
int w[101];
int v[101];
int dp[101][100001];
int n, k;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (j - w[i] >= 0) { // 만약 무게한도 내라면
dp[i][j] = max(dp[i-1][j], dp[ i- 1][j - w[i]] + v[i]); // 점화식
} else{
dp[i][j] = dp[i-1][j]; // 아니라면 이전값
}
}
}
cout << dp[n][k];
}
Reference
この問題について(恥ずかしい質問), 我々は、より多くの情報をここで見つけました https://velog.io/@blacklandbird/냅색-문제テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol