読者です 読者をやめる 読者になる 読者になる

真面目なノート

こまめにその日の進捗などをメモしておく。

研究が危険で危ない

競技プログラミング HTML,CSS

今日のまとめ

  • プログラミング
  • バイ
    • iOSSafariでスクロールぼよんぼよん
  • 研究
    • 水曜日のグループミーティング用スライド作成
    • 論文 ClimbAware

プログラミング

AOJで競技プログラミングの練習

Knapsack Problem | Aizu Online Judge

先日は0-1ナップザック問題を動的計画法で解いたが、今日は個数制限の無いナップザック問題である。

0-1ナップザック問題は解の表を埋めていく際に、上と斜め上のセルを参照した。個数制限の無いナップザック問題においては、同じ種類の品物を複数個入れることが許されているため、上と左のセルを参照すれば良い。プログラムで言えば、0-1ナップザック問題との違いは、表の更新のタイミングだけになる(と思う)。

"""
0-1ナップザック問題の解答
"""
l = input().split()
N = int(l[0])
W = int(l[1])
products = [] # [[value, weigth]]
for i in range(N):
    l = input().split()
    products.append([int(l[0]),int(l[1])])

DP = [0 for _ in range(W+1)]
p_flag = [[False for _ in range(N)] for _ in range(W+1)]
for i in range(N):
    new_DP = [DP[j] if j < products[i][1] else 0 for j in range(W+1)]
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            new_DP[j] = product_in
        else:
            new_DP[j] = DP[j]
    DP = [v for v in new_DP]
print(DP[W])
"""
ナップザック問題の解答
"""
l = input().split()
N = int(l[0])
W = int(l[1])
products = [] # [[value, weigth]]
for i in range(N):
    l = input().split()
    products.append([int(l[0]),int(l[1])])

DP = [0 for _ in range(W+1)]
for i in range(N):
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            DP[j] = product_in
        else:
            DP[j] = DP[j]
print(DP[W])

流石に、前回の0-1ナップザック問題とほぼ同じであるため、時間を書けず解答することができた。

バイ

バイト先で書いているコードを書いた。HTMLとJSなので、そこまで色々と書くような技術的知見を得られたわけではないが、今後のためにメモはとっておく。

iOSSafariにおいて、ウェブページの上端・下端を越えてスクロールしようとすると、少しだけ動いて元に戻る、というような動作をする。ぼよんぼよん、という感じの動作のことである。

これはシングルページアプリで、横方向にだけ画面が動くというようなものを作るときに若干不便になる。そのようなときは、以下のようにしてfixにするとよい。

position: fixed;

iOS特有のぼよんぼよんはfixed、absoluteの要素には適用されないらしく、これで一先ず動かなくなる。