变身缎带 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 java代码写在记事本上后在cmd上运行时无报错但又没生成文件
  • ¥15 关于#python#的问题:在跑ldsc数据整理的时候一直抱这种错误,要么--out识别不了参数,要么--merge-alleles识别不了参数(操作系统-linux)
  • ¥15 PPOCRLabel
  • ¥15 混合键合键合机对准标识
  • ¥100 现在不懂的是如何将当前的相机中的照片,作为纹理贴图,映射到扫描出的模型上
  • ¥15 魔霸ROG7 pro,win11.息屏后会显示黑屏,如图,如何解决?(关键词-重新启动)
  • ¥15 有没有人知道这是哪里出了问题啊?要怎么改呀?
  • ¥200 C++表格文件处理-悬赏
  • ¥15 Windows Server2016本地登录失败
  • ¥15 复合卡卡号轨道写入芯片卡