0-1バックパックテンプレート

0-1バックパックの問題
例:
タイトル
N個の品物とV容量のリュックサックがあります.i番目の品物の費用はc[i]、価値はw[i]です.リュックサックにどのアイテムを入れるかを解くと、価値の合計が最大になります.
解析:これは最も簡単な0-1リュックサックの問題で、特徴は:すべての品物は1つだけあって、置くか置かないかを選ぶことができます.
0-1リュックサック問題の特徴:
1.2つの状態のみ
2.各要素の数が1(ある要素の数が1ではなく、nである場合があるが、n種類の数が1の要素に変換することで、0-1リュックサックの問題に変換できる)
コードは次のとおりです.

/*
n--   n   
m--      
cost[i]--    i          
val[i]--    i       
f[i]--        i ,                 
*/ 
for(i=1;i<=n;i++)
{
	for(j=m;j>=cost[i];j--)
	{
		f[j]=max(f[j],f[j-cost[i]]+val[i]);
	}
}