题目大意： 给出骨头的价值和重量，用体积为V的背包装这些骨头，求最大价值
大致思路： 这里为01背包的讲解 http://blog.csdn.net/Remilitarize/article/details/55666889
C：（二维数组）
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=1010;int value[maxn],weight[maxn];int dp[maxn][maxn];int main(){ int n; while(scanf("%d",&n)!=EOF){ while(n--){ int a,b,i,j; scanf("%d%d",&a,&b); //a为骨头数量，b为背包容量 memset(dp,0,sizeof(dp)); //初始化 for(i=1;i<=a;i++) scanf("%d",&value[i]); for(i=1;i<=a;i++) scanf("%d",&weight[i]); for(i=1;i<=a;i++) //选取第i个骨头 for(j=0;j<=b;j++) //当前背包容量为j if(j>=weight[i]) //如果第i个骨头能够装入背包 dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]); /*不装骨头为dp[i-1][j]，装骨头为把第i个骨头的重量去掉对应容量的dp[i-1][j-weight[i]并加上这个骨头的价值value[i]*/ else dp[i][j]=dp[i-1][j]; PRintf("%d/n",dp[a][b]); //a个骨头全部装进去并当前容量为b的最大价值 } } return 0;}C：（一维数组）
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=1010;int value[maxn],weight[maxn];int dp[maxn];int main(){ int n; while(scanf("%d",&n)!=EOF){ while(n--){ int a,b,i,j; scanf("%d%d",&a,&b); memset(dp,0,sizeof(dp)); for(i=1;i<=a;i++) scanf("%d",&value[i]); for(i=1;i<=a;i++) scanf("%d",&weight[i]); for(i=1;i<=a;i++) for(j=b;j>=weight[i];j--) //注意要从后向前 dp[j]=max(dp[j],dp[j-weight[i]]+value[i]); printf("%d/n",dp[b]); } } return 0;}新闻热点
疑难解答
