动态规划01背包问题求解(附c/cpp代码)

• • 1. 问题描述
  • 2. 输入格式
  • 3. 输出格式
  • 4. 输入样例
  • 5. 输出样例
  • 6. 问题分析
  • 7. 代码实现
  • 8. 执行结果

有 n 种物品和一个容量是 y 的背包，每种物品只有一件。

第 i 种物品的体积是 wi，价值是 vi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值和物品序号。

第一行两个整数，N，Y，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数wi，vi，用逗号隔开，分别表示第 i 种物品的体积和价值。

输出最大价值，物品序列号。

3,10
5,8
8,20
4,17

最大价值：25
物品序号：3号 1号 

#include 
#include 
using namespace std;

typedef struct {
    int w;
    int v;
}Object;

int main(){
    int n,y;
    char ch;
    cin>>n>>ch>>y;
    Object ob[n+1];
    for(int i=1;i<=n;++i)
        cin>>ob[i].w>>ch>>ob[i].v;//ob[0]未使用
    int arr[n+1][y+1];
    for(int i=0;i
            arr[i][j] = arr[i-1][j];
            if(ob[i].w <= j)
                arr[i][j] = max(arr[i-1][j],arr[i-1][j-ob[i].w]+ob[i].v);
        }
    vector  r;
    int j = y;
    for(int i=n;i>0;--i)
        if (arr[i][j] != arr[i-1][j]){
            r.push_back(i);
            j = j - ob[i].w;
        }
    cout<<"最大价值:"<::iterator it = r.begin();it!=r.end();++it)
        cout<<*it<<"号 ";
    return 0;
}

10,30
2,3
5,6
8,6
10,12
6,7
9,11
4,7
6,8
7,8
5,8
最大价值:41
物品序号:10号 7号 6号 4号 1号
Process returned 0 (0x0)   execution time : 1.365 s
Press any key to continue.

——————END-2022-04-23——————
———————感谢您的阅读—————————