蓝桥杯算法提高VIP-01背包

解题思路:

注意事项:

参考代码:

#include "stdio.h"

int max(int a,int b){

return a>b?a:b;

}

int main()

{

int num,weight;

int i,j;

scanf("%d%d",&num,&weight);

int w[num+1];

int v[num+1];

int dp[num+1][weight+1];

for(i=1;i<=num;i++){

scanf("%d%d",&w[i],&v[i]);

}

for(i=0;i<=num;i++){

dp[i][0]=0;

}

for(i=0;i<=weight;i++){

dp[0][i]=0;

}

for(i=1;i<=num;i++){

for(j=1;j<=weight;j++){

if(j<w[i]){

dp[i][j]=dp[i-1][j];

}

else{

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

}

}

}

printf("%d",dp[num][weight]);

return 0;

}