小明有一个容量为 V的背包。
这天他去商场购物，商场一共有 N 件物品，第 i 种物品的体积为w[i]，价值为 v[i]
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。
1≤N≤10^3，1≤V≤10^3，1≤w[i],v[i]≤10^3。
#include
#include
int dp[1001][1001]={0};
void package (int n,int v,int *w,int *c){
for(int i=1;i=w[i]&&dp[i-1][j-w[i]]+c[i]>dp[i-1][j])
dp[i][j]=dp[i-1][j-w[i]]+c[i];
else dp[i][j]=dp[i-1][j];
}
}
}
int main(int argc, char *argv[])
{
int n,v;
scanf("%d %d",&n,&v);
int w[1000]={0};
int c[1000]={0};
for(int i=1;i 有人会问啦，“为什么dp数组初始化大小要设为1001那么多，题目要求N和V都是小于等于1000的啊？”
这是因为啊，在这里遍历dp数组的时候，要将第一个状态从dp[1][1]开始存入，i和j的初始值都设为了 1 ，C语言数组长度为n，下标就是0—n-1，要想从下标1开始，那么你的数组定义长度就要比题目给的范围大1。
这样才能保证不越界。
在函数调用数组的位置，我就在第一次写这道题的时候就犯了错，所以把它写进易错点。
正确的在函数头调用数组及指针的格式是：类型+“空格”+“*”+数组名
而在主函数中调用函数的时候括号里面直接敲数组名就够了
易错点02：这一步就是状态转移方程 用来比较选择放第i件 和 选择不放第i件那个价值更大，然后把值大的一个赋值给dp[i][j]；要注意的就要提前判断一下 j 和w[i]的大小，因为如果没有比较的话，j-w[i]会出现负值，error：数组的下标越界；
易错点03：在循环输入w[i],c[i]的代码当中的for循环使用上要注意，
总结了一下，这里的会出现以下错误情况
一种错误：
这样会出现报错越界情况，原因就在于数组就只能又数组长度n个位置可以填入，下标是0—n-1如果是for（i=1；i<=n;i++)到最后会出现i=n这一情况。
上面这是正确而且能通过题目的代码，可是仔细看一下，这个正确的代码和上面错误的代码就只有i的条件上不一样。
一个是i
。
我也不知道为什么，还请各位给我讲讲。
另一种错误：
这样的形式也是错的，虽然不会出现越界的报错，但是数组是从a[0]开始保存的，是不符合题意的
更改方法就是将a[i]变成a[i+1]。
如图：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）