2 qq 33070397 qq_33070397 于 2016.04.28 17:08 提问

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

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

题目如下:

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
CSDNXIAOC   2016.04.28 17: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,以上是依据我对问题的理解给出的答案,如果解决了你的问题,望采纳。

NK_test
NK_test   Rxr 2016.04.29 22:42

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

qq_36412483
qq_36412483   2017.08.17 14:33

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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
0-1背包问题 动态规划源码
0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码
动态规划之详细分析0-1背包问题
题目:   有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 w[i],价值是 p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。   本文按照动态规划的标准模式解析:http://blog.csdn.net/hearthougan/article/details/53749841  0-1背包问题,表示的是每个物品只有一件,每件物品不能分割
动态规划算法0-1背包问题java实现
import java.util.ArrayList; import java.util.HashMap; /* * 实际就是一种分而治之的思想 每次加入新物品i的时候,将总的容量-物品i的容量即是前i-1种物品可以使用的,得出
算法java实现--动态规划--0-1背包问题
0-1背包问题算法的java实现(动态规划法) 具体问题描述以及C/C++实现参见网址 http://blog.csdn.net/liufeng_king/article/details/8683136 以下为we
0/1背包问题动态规划 空间复杂度是o(C)
有num个物品,总背包容量为Capacity, 求不超过背包总容量的前提下使得背包里的物品的价值达到最大的物品是哪些物品。 对于每个物品,只有两种选择,要么装要么不装进背包。 那么在考虑前 i 个物品时,在当前容量为 j 的条件下,如果这个物品的体积小于当前背包剩下体积,且装入此物品的价值比不装此物品的价值大,就装入此物品 ,设第 i 个物品的体积为 vol[ i ] ,价值 为 va
0-1背包问题(动态规划)附例题详解——java实现
0-1 背包问题(java实现)代码在最后    给定 n 种物品,每种物品有对应的重量weight和价值value,一个容量为 maxWeight 的背包,问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?面对每个物品,我们只有选择拿取或者不拿两种选择,不能选择装入某物品的一部分,也不能装入同一物品多次。使用动态规划思想,很容易想到,我们需要一个空间来储存:从0号物品开始,对于每...
0-1背包问题;动态规划;时间复杂度O(n方);给出最大价值与解得情况;内有动态规划思路总结;
#include using namespace std;//动态规划:0-1背包问题//bestValue[i][j]=max ( bestValue[i+1][j-w[i]]+v[i] ,bestValue[i+1][j] ) w[i]<=j//bestValue[i][j]=bestValue[i+1][j] w[i]>jclass Knapsac
动态规划法解决0-1背包问题(C++)
1.动态规划法的设计思想:动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段,子问题的重叠关系一般表现在对给定问题求解的递推关系,将子问题的的解求解一次并且填入表中,当需要再次求解子问题的时候,可以通过查表获得这个子问题的解而不是再次求解,从而避免大量重复计算,为了达到这个目的,可以通过一个表来记录所有以解决的子问题的解。 2.动态规划法求解的问题的特征:该问题的
0-1背包问题与动态规划的C/C++代码
那一年, 非计算机专业的我听到0-1背包和动态规划, 觉得很高大上, 其实, 动态规划无非就是寻找高中数学中所说的递推公式而已。最近又复习到0-1背包问题和动态规划, 所以打算用代码来玩玩。        0-1背包问题: 一个小偷来出来活动了, 拿了一个背包, 最多可以装50斤的东西的小袋子。 他眼睛一亮, 发现了三件宝贝a, b, c.   其中a重10斤, 价值60元; b重20斤
0/1背包问题 - 动态规划(C++实现)
0 / 1背包问题 - 动态规划(C++实现)flyfish以下代码在VC++2013下编译通过#include "stdafx.h" #include <iostream> #include <algorithm> #include <vector> struct Item //物品定义 { int id, weight, value;//编号,重量,价值。编号为0的物品这里没有使用