渴望被问路的and 2023-02-04 14:01 采纳率: 100%
浏览 24
已结题

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

有 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日

    悬赏问题

    • ¥30 频率与占空比均可调的方波发生器
    • ¥15 VB6.0中PICTUREBOX加载本地图片无法显示
    • ¥100 关于游戏app session获取的问题
    • ¥15 MYSQL数据库建表
    • ¥15 爬虫程序爬取TTGChina网站文章代码
    • ¥35 由于系统缓冲区空间不足或队列已满,不能执行套接字上的操作。
    • ¥15 如何用下图方法在AMESim中搭建离心泵模型
    • ¥15 C#连接服务器,请求时报Ssl/Tsl未能建立安全通道
    • ¥15 xcode15build的c++ dylib在10.15上不兼容
    • ¥15 CPLD如何实现在线逻辑分析