BYR Achieve · 镜像论坛

一个关于01背包的问题，代码运行错误~求指教

2017/3/28镜像同步1 回复

问题：题目描述众所周知，刘同学有个外号叫叮当猫，因为每当你需要什么，他就会给你提供什么，仿佛没有什么东西是他没有的。当然，这源于他平时对物品的收集比较到位。假设他有一个容量为V大小的工具箱来存放他的物品，为了感谢他平日里的无偿帮助，同志们给了他凑了一笔钱，让他可以充实他的工具箱，他开心的来到京狗，发现不同的工具有不同的价值和不同的体积，现在给出你所有商品的价格和体积，在工具箱容量允许的范围内，请你帮他求出他所能买的物品的最高价值。假设每种物品只能买一次，同志们给他凑的钱足够他使用。输入第一行包含一个整数N，为测试样例的个数其次N个测试样例，每个三行。第一行包含两个整数n，V，（n < = 1000，V < = 1000）代表商品的数量和他工具箱的体积。第二行包含n个整数表示每个商品的价值。第三行包含n个整数代表每个商品的体积。输出输出他工具箱能买的商品的最大价值样例输入 1 5 10 1 2 3 4 5 5 4 3 2 1 样例输出 14 代码： #include<stdio.h> #define PI 1001 int dp[100][100]; int max(int a,int b) { if(a>=b) return a; else return b; } int Rec(int n,int V,int w[],int v[],int x[]) { int i,j; for(i=0;i<=n;i++) { dp[i][0]=0; } for(j=0;j<=V;j++) { dp[0][j]=0; } for(i=n;i>=1;i--) { for(j=0;j<=V;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]); j=V; for(i=n-1;i>=0;i--) { if(dp[i][j]>dp[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } } } return dp[n-1][V]; } int main() { int n,V; int w[PI],v[PI],x[PI]; int i,max; scanf("1"); scanf("%d %d",&n,&V); for(i=0;i<n;i++) { scanf("%d ",&w[i]); } for(i=0;i<n;i++) { scanf("%d ",&v[i]); } max=Rec(n,V,w,v,x); printf("%d",max); return 0; }

订阅后，新回复会通过你的通知中心匿名送达。