リュックサックの問題

https://www.acmicpc.net/problem/1535
https://www.acmicpc.net/problem/12865
シルバー2安寧問題とゴールド5普通リュックサック問題.入力値の範囲が違うだけで、実は同じ問題なので、一度整理学習...
リュックサックの問題はリュックサックに最大の重量と、それぞれの重量と価値のあるものを与え、リュックサックに最も価値のある(?)これは質問方法の問題です.入力値が十分小さい場合は、簡単な複文で解決することもできますが、もちろん与えません.恐ろしいDPで解きほぐす.
私はDP表を作っていないので、他の文章を真剣に読んで理解することに満足しています.後で忘れたら、整理してあなたに分かるようにします.
まず,dpテーブルの大きさは(品数)*(リュックの最大重量+1)であり,基本的なリュックの問題は解決されたようである.
問題はこのテーブルの意味です.
dp[i][j]とは、最大重量jのリュックサックの中で0~i番のものが最も価値がある場合の価値を意味する.

i件目の重量がリュックサックの最大容量jより大きいと、リュックサックさえ入れられなくなります.したがって、dp[i][j]の値はdp[i-1][j]の値に等しい.dp[i-1][j]は、iの1番目のものを除いて、0からi-1のものまでの最大の価値である.

i件目の重量がjより小さい場合は、リュックサックに入れることができます.ここではiがリュックサックに入っているのが有利か不利かを見ます.含まない場合はdp[i-1][j]の値になります.では、荷物を詰めるときはどうすればいいのでしょうか...ここは難しいと思います.結論的にはdp[i-1][j-(i 1番目のものの重さ)]+(i 1番目のものの価値)です.dp[i-1][j-(iの最初のものの重さ)]は、最大値jのバッグに0からi-1のものが入っていることを意味し、iの最初のものがiの最初のものの重さを残し、最も価値のあるものと考えられる.さらにiの1番目のアイテムの価値を加えれば、iの1番目のアイテムを含む場合、リュックサックは最も価値のあるものになります.ここで、前述したように、両ケースを比較し、より価値のあるものをdp[i][j]に記憶すればよい.

上記の手順でdpテーブルを記入すると、テーブルの右下隅の値が正解になります.
まずS 21535号の質問です
この問題はリュックの重さではなく、体力です.最大体力が100で100を失うと死んでしまい、99しか使えません.体力と価値の代わりに快楽を使うだけで、同じ問題を示した.

from sys import stdin

n = int(stdin.readline())
lose = list(map(int, stdin.readline().split())) # 잃는 체력
joy = list(map(int, stdin.readline().split())) # 얻는 기쁨

dp = [[0 for i in range(100)] for j in range(n)]

for i in range(n):
    for j in range(100):
        if i == 0:
            if lose[i] > j:
                dp[i][j] = 0
            else:
                dp[i][j] = joy[i]
        else:
            if lose[i] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - lose[i]] + joy[i])

print(dp[-1][-1])

G 5 12865号普通リュック問題
重量の範囲は100000まで増加した.でもdpで解くと何の違いもありません

from sys import stdin

n, k = map(int, stdin.readline().split())
items = [list(map(int, stdin.readline().split())) for i in range(n)]

dp = [[0 for i in range(k+1)] for j in range(n)]

for i in range(n):
    for j in range(1, k+1):
        if items[i][0] <= j:
            dp[i][j] = max(dp[i-1][j-items[i][0]] + items[i][1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])

他にもいくつか質問を読みましたが、もう少し追加すると頭が痛くなります.いつdpに適応できるか分からない.