完全リュック問題ダイナミックプランニングc++

完全なリュックサック問題
【問題の説明】
n種類の物品が設けられており、各物品には重量と価値がある.しかし、それぞれの品物の数は無限で、同時に1つのリュックサックがあって、最大積載重量はMで、今n種類の品物の中からいくつかのもの(同じ品物は何度も選択することができます)を選んで、その重量の和がMに等しくないようにして、価値の和は最大です.
【入力形式】
1行目:2つの整数、M(リュックサック容量、M<=200)とN(物品数、N<=30);
2.N+1行:行ごとに2つの整数Wi,Ciがあり、各物品の重量と価値を表す.
【出力形式】
1行のみ、1つの数で、最大の総価値を表します.
【サンプル入力】knapsack.in
     10  4
     2  1
     3  3
     4  5
     7  9
【サンプル出力】knapsack.out
　 max=12
 
次に解決しなければならないのは完全リュックの問題で、01リュックより完全リュックの問題が異なるのは、すべてのリュックの数が無限大であることです.だから物iに対して、私达がしなければならないのはiをプラスするか、iをプラスしないかを选ぶだけではなくて、1,2,3をプラスします......个i小妖精【x
同様に、前i個の物品をf[i][v]で表し、総重量がvを超えない場合の最大値を表す.kがi物品の数であると仮定すると,c[i]が毎回加算されるのはk−1の最適解であるべきである.すなわち
f[i][v]=max(f[i-1][v],f[i][v-w[i]]+c[i])
注意しなければならないのは、完全なリュックの中で、私達は小さい時から大きい順に品物iの数量を増加して、それでは相応のvの値も絶えず大きくなって、だからvの循環は1--mから(額のこの点は実は私もよく分かりませんO(∩∩)O||ハハ~)
 
プログラムを添付

#include
#include
using namespace std;
int m,n,w[31],c[31],f[31][201];

int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;++i)
	scanf("%d%d",&w[i],&c[i]);
	for(int i=1;i<=n;++i)
	for(int v=m;v>=0;--v)
	{
		if(v-w[i]>=0)
		f[i][v]=max(f[i-1][v],f[i][v-w[i]]+c[i]);
		else f[i][v]=f[i-1][v];
	}
	cout<