变身缎带 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日

悬赏问题

  • ¥15 Python信息系统tkinter代码错在哪里
  • ¥15 FOR循环语句显示查询超过300S错误怎么办
  • ¥15 个人通讯录管理系统 C语言 程序设计 需要能运行成功的 结构体和数组 Visual C++编译器
  • ¥15 数电设计题 没有设计思路 不知道用什么芯片进行设计 求提供设计思路
  • ¥15 在动态多目标优化问题中,第一幅图展示的是问题DF6的相关定义和绘制的POS和POF图,请问图中公式PS(t)和PF(t)是如何推导的
  • ¥60 先数学建模,接着设计一种优化算法结合案例给出智能仓储四向穿梭车的调度计划
  • ¥15 Errno2:No such file or directory,在当前文件确实没有该图片,怎么解决?
  • ¥15 博世摄像头数据存储的问题(iscsi)
  • ¥15 如何实现对学生籍贯信息管理系统的选择排序
  • ¥15 写一个51单片机的时钟代码