法一:普通递归
include[HTML_REMOVED]
using namespace std;
const int M = 110;
int V,N;
int v[M],w[M],s[M];
int f(int i ,int j)
{
int n = 0;
if(j == 0) return 0;
if(i >= 1)
{
for(int k = 1 ; k <= s[i] && k * v[i] <= j ; k++)
{
n = max(n , f(i - 1 , j - k * v[i]) + k * w[i]);
}
return max(n , f(i - 1 , j));
}return = 0;
}
int main()
{
cin >> N >> V;
for(int i = 1 ;i <= N ; i++) cin >> v[i] >> w[i] >> s[i];
cout << f(N,V);
return 0;
}
法二:记忆化递归
include[HTML_REMOVED]
using namespace std;
const int M = 110;
int V,N;
int v[M],w[M],s[M];
int mem[M][M];
int f(int i ,int j)
{
if(mem[i][j] != 0) return mem[i][j];
int n = 0;
if(j == 0) mem[i][j] = 0;
if(i >= 1)
{
for(int k = 1 ; k <= s[i] && k * v[i] <= j ; k++)
{
n = max(n , f(i - 1 , j - k * v[i]) + k * w[i]);
}
mem[i][j] = max(n , f(i - 1 , j));
}else mem[i][j] = 0;
return mem[i][j];
}
int main()
{
cin >> N >> V;
for(int i = 1 ;i <= N ; i++) cin >> v[i] >> w[i] >> s[i];
cout << f(N,V);
return 0;
}
法三: 用数组模拟递归
include[HTML_REMOVED]
using namespace std;
const int M = 110;
int V,N;
int v[M],w[M],s[M];
int f[M][M];
int main()
{
cin >> N >> V;
for(int i = 1 ;i <= N ; i++) cin >> v[i] >> w[i] >> s[i];
for(int i = 1 ; i <= N ; i++)
{
for(int j = 1 ; j <= V ; j++)
{
for(int k = 0 ; k <= s[i] && j >= k * v[i] ; k++)
f[i][j] = max(f[i][j] , f[i - 1][j - k * v[i]] + k * w[i]) ;
}
}
cout << f[N][V];
return 0;
}