for でループの第4夜

はい。
[http://d.hatena.ne.jp/shindannin/20111202/1322833089]
(http://d.hatena.ne.jp/shindannin/20111202/1322833089)
より。

問題4 0-1ナップサック問題
品物がN種類（重量weight[i]、価値 value[i]、0≦i＜N）があります。
ナップサックには、合計で重量Wまで、品物をつめることができます。
それぞれの品物は最大で1つだけしか選べません。
あなたは、詰める品物の価値の合計が最大になるように、ナップサックに品物を詰めたいです。
そのときの価値の合計を最大値はいくらでしょう？

入力・制約条件

int N: Nは、1≦N≦20を満たす整数
int W: Wは、0≦N≦10000000を満たす整数
vector <int> weight: weightの要素数はN個。1≦weight[i]≦10000000 を満たす整数
vector <int> value:  valueの要素数はN個、 1≦value[i] ≦10000000  を満たす整数

例1
入力:N=5,W=10,weight={1,2,3,4,3} value={2,5,10,2,6}
出力:23
0番目・1番目・2番目・4番目のを詰めると、重量1+2+4+3=10、価値2+5+10+6=23でベストです。

```py:a.py

#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import print_function
import sys
import io
import re
import math

N = 5
W = 10
weight = [1,2,3,4,3]
value = [2,5,10,2,6]

max_value = -1
for all_count in range(1<<N):
    sum_weight = 0
    sum_value = 0
    for i in range(N):
        if (all_count >> i & 1):
            sum_weight += weight[i]
            sum_value += value[i]
    if sum_weight <= W:
        max_value = max(max_value,sum_value)
print (max_value)

```

```py:他の問題とかに使うときこういう書き方かな.py

youso = 与えられる要素数(色数やナップサック)
seigen = 選べるのは2色までや重量10以下の制限

max_value= -1
#一番外側はどうやらrange(1<<要素数)で書くっぽい。
for all in range(1<<youso):
#各組み合わせから出てくる重量、価値の初期値を0にする
    sum_weight = 0
    sum_value = 0

#ちょっとわかってない要素数ループ
    for i in range(youso):
#ビットチェックの別方法。 らしい。。。
#ビットが立っている(1)なら使っていると判定して、立っていない(0)なら使っていないと判定かな。。。
        if (all>>i & 1):
#使っていると判定された要素の重量と価値を加算する
            sum_weight += weight[[i]
            sum_value += value[i]
    if sum_weight<=W:
#初回はmax_valueが-1になっているのでsum_valueの値が代入される。
#2回目以降は大きい方の数値がmax_valueに代入されるっぽい。
        max_value = max(max_value,sum_value)
print max_value

```

んんー、これどんどん使っていかないとわかるようにならないな。。

追記
使ってみたけど上手く動いてくれなかった
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B)

How many ways?
1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。

例えば、1 から 5 までの数から３つを選んでそれらの合計が 9 となる組み合わせは、

1 + 3 + 5 = 9
2 + 3 + 4 = 9
の２通りがあります。

に対して書いたのが

```py:a.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import time
import sys
import io
import re
import math
l = []
ans=0
(n,x)=map(int, raw_input().split())
for a in range(1,n+1):
    l.append(a)
for sou in range(1<<n):
    sum_weight=0
    sum_value=0
    for i in range(n):
        if (sou >> i & 1):
            sum_value+=l[i]
            sum_weight+=1
    if sum_value==x and sum_weight==3:
        ans+=1
print ans 
```
提出前に何パターンか試してみると20 20辺りからもうファンが猛烈に回って大変な惨状に。。。
ここを直せばとか、コレを読めば分かるよなどの誘導先あったらよろしくお願いします。


回答提出自体はfor3重で済ませました。。

```py:for3重.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import timeit
import time
import sys
import io
import re
import math
#start = time.time()
#start = time.clock()
while True:
    l = []
    (n,x)=map(int, raw_input().split())
    if n==x==0:
        break
    ans=0
    for a in range(1,n+1):
        l.append(a)
    for i in l:
        if i > 98: break
        for j in l:
            if j > 99 or i+j>x: break
            p=0
            for k in l:
                p=i+j+k
                if (i != j and j != k and k != i) and p==x and i<j<k:
                    ans+=1
    print ans
```