(欲張り)1次元配列は完全なリュックサックの問題を解く(品物は無限に繰り返すことができる)--アルゴリズムノート

  ： 
 n       m      i                  
                   
  ：
            ！	
               ，         f[] 

#include

using namespace std;

int w[500],v[500];
int f[500];

int main()
{
    int n,m;
    cin>>n>>m;
       
    for(int i=1;i<=n;i++)
	{
        cin>>w[i]>>v[i];
    }
    
    for(int i=1; i<=n; i++)
	{
		for(int j=w[i]; j<=m; j++)
		{
			//f[j] max { f[j],f[j-w[i]] + v[i] }
        	if( f[j-w[i]]+v[i] > f[j] )		//  i         	//  f[]        
        	{
        		f[j] = f[j-w[i]]+v[i];
			}	
    	}
	}
    
    cout<<f[m]<<endl;//   
   
}