变身缎带 2023-02-04 14:01 采纳率: 100%
浏览 27
已结题

解背包问题算出来答案不对,不知道代码哪里不对

有 N件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N行,每行两个整数 vi,wi,用空格隔开,分别表示第 i件物品的体积和价值。

输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8

我是这样写的


```c++
#include <iostream>
using namespace std;
int main()
{
    int N,V;
    cin>>N>>V;
    int a[1000][1];
    int i;
    for(i=0;i<N;i++)
    {
        cin>>a[i][0]>>a[i][1];
    }
    int b[1000];
    int k=0;
    for(i=0;i<N;i++)
    {
       for(int j=i+1;j<N;j++)
       {
            if(a[i][0]+a[j][0]<=V)
            {
            b[k]=a[i][1]+a[j][1];
            k++;
            }
       }
    }
    int max=b[0];
    for(i=1;i<=k;i++)
    {
        if(b[i]>max)
        {
            max=b[i];
        }
    }
    cout<<max;
    return 0;
}

结果算出来答案不对,是哪里出了问题

  • 写回答

1条回答 默认 最新

  • 社区专家-Monster-XH 2023-02-04 15:09
    关注

    只能解决恰好两个物品的情况。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 2月12日
  • 已采纳回答 2月4日
  • 创建了问题 2月4日

悬赏问题

  • ¥20 机器学习能否像多层线性模型一样处理嵌套数据
  • ¥20 西门子S7-Graph,S7-300,梯形图
  • ¥50 用易语言http 访问不了网页
  • ¥50 safari浏览器fetch提交数据后数据丢失问题
  • ¥15 matlab不知道怎么改,求解答!!
  • ¥15 永磁直线电机的电流环pi调不出来
  • ¥15 用stata实现聚类的代码
  • ¥15 请问paddlehub能支持移动端开发吗?在Android studio上该如何部署?
  • ¥20 docker里部署springboot项目,访问不到扬声器
  • ¥15 netty整合springboot之后自动重连失效