完全背包问题的二维数组实现方法

创作时间:

作者:

@小白创作中心

完全背包问题的二维数组实现方法

引用

CSDN

https://blog.csdn.net/weixin_53824622/article/details/140009493

完全背包问题与0-1背包问题的主要区别在于物品的选取次数：0-1背包问题中每个物品只能选取一次，而完全背包问题中每个物品可以无限次选取。本文将通过一个具体示例，详细介绍如何使用二维数组来解决完全背包问题。

问题描述

设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于M，而价值的和为最大。

输入格式

第一行：两个整数，M（背包容量，M<=200）和N（物品数量，N<=30）；
第2..N+1行：每行两个整数Wi,Ui，表示每个物品的重量和价值。

输出格式

仅一行，一个数，表示最大总价值。

输入样例

输出样例

代码实现

#include<iostream>
using namespace std;
int w[201],c[31];
int value[201][201];//第一个参数代表的是前n件物品，后一个参数代表的是物品的价值。 
int main(){
    int m,n;//m,n分别代表背包容量和物品数量。
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>c[i];//w和c分别代表容量和价值。 
    for(int i=1;i<=n;i++)//先遍历物品。
    {
        for(int j=1;j<=m;j++)//再遍历背包。 
        {
            //如果当前背包容量小于物品容量，那么无法放入到背包中，背包的价值依旧是前一个容量的价值。 
            if(w[i]>j){
                value[i][j]=value[i-1][j]; 
            } 
            //如果当前背包容量大于物品容量，那么这时候可以选择放与不放，看下这两种情况哪种价值大。 
            if(j>=w[i])
            value[i][j]=max(value[i-1][j],value[i][j-w[i]]+c[i]);
        }
     } 
     cout<<value[n][m];
}