qq_33070397
qq_33070397
采纳率62.5%
2016-04-28 09:08 阅读 3.6k

0-1背包问题(动态规划)

代码敲出来了但是提交是错的,我也不知道为什么了,题目和代码都在下面,帮我看看吧!!!

题目如下:

Problem Description

给定n种物品和1个背包,物品i的重量是wi,其价值为vi,背包的容量为C。要求选择装入背包的物品,使得装入背包中物品的总价值最大。

Input

每组测试数据包含3行,第1行为n和c,表示有n(0<=n<=400)个物品且背包容量为c (c<=1500),第二行为这n个物品的重量wi(1<=wi<=1000),第三行为这n个物品的价值vi。背包容量和物品重量都为整数。

Output

输出装入背包的最大总价值,每个答案一行。

Sample Input
5 10
2 2 6 5 4
6 3 5 4 6
Sample Output
15

代码如下:
#include
using namespace std;
int MAX(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,m;
while(cin>>n>>m)
{
int i,v[500],w[500],x[500][2000];
for(i=1;i<=n;i++)
{
cin>>w[i];
}
for(i=1;i<=n;i++)
{
cin>>v[i];
}
fill(&x[0][0],&x[n][m]+1,0);
int o=0;
for(i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j>=w[i])
{
x[i][j]=MAX(x[i-1][j],x[i-1][j-w[i]]+v[i]);
}
else
x[i][j]=x[i-1][j];
if(x[i][j]>o)
o=x[i][j];
}
}
cout<<o<<endl;
}
return 0;
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

3条回答 默认 最新

  • CSDNXIAOC Robot-C 2016-04-28 09:12

    动态规划:0/1背包问题
    1、问题简介
    2、方法
         动态规划,主要用到的公式见下面(符号意思见代码处解释)
    3、详细代码实现
    4、效果截屏

    3、解决代码
    // 动态规划法求0/1背包问题
    // by 孙琨SealSun at UCAS
    // 2015.11.19
    #include
    using namespace std;
    #define MAX 256......
    答案就在这里:动态规划:0/1背包问题
    ----------------------你好,人类,我是来自CSDN星球的问答机器人小C,以上是依据我对问题的理解给出的答案,如果解决了你的问题,望采纳。

    点赞 1 评论 复制链接分享
  • qq_36412483 肥宅_小清新 2017-08-17 06:33

    哈哈哈哈哈。我看了你的代码,终于找到问题了。贼有趣。居然是内存问题。你这要的内存太高了。用滚动数组做。我今天刚好打了一个。

    点赞 1 评论 复制链接分享
  • NK_test NK_test 2016-04-29 14:42

    你确认if那写的是0而不是字母o?

    点赞 评论 复制链接分享

相关推荐