恥ずかしい質問

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の場合、リュックの最大値の和に入る.

i番目のものの虹はw[i]、価値はv[i].

パックにi次品が入っていない場合、最大値はdp[i-1][j]となる.

iがiを加えると、dp[i-1]j-w[i]+v[i]が最大値となる.

例えば、dp[3][6](春から3番目のアイテム、6はリュックの容量)の場合、

MAX(dp[2][6],dp[2]6-w[3]+v[3]).

完全なコード

#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];
}