恥ずかしい質問

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