0-1背包（动态规划经典算法题）

任务描述

给定n个物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

相关知识

动态规划

输入格式

第一行输入一个n，c，代表有n个物品背包容量为c
接下来n行，每行输入wi，和vi
其中0 输出格式

输出一个数，代表最大价值。

输入

4 8
2 3
3 4
4 5
5 6

输出

10

搞清楚状态转移方程是重点！

装第i个物品时：

①当装不下第i个物品时，dp[i][j]等于上一个，也就是dp[i-1][j]

②当装得下第i个物品时，但是装了也不一定能达到当前最优价值，所以在装与不装中选择最优的一个，dp[i][j]=max（dp[i-1][j]，dp[i-1][j-w[i]]+v[i]）； 

温馨提示：

Ⅰ. dp【】【】的一维数组的下标是从1开始的，到n（物品个数）结束

Ⅱ. j表示当前背包剩余容量 

Ⅲ.，第二层循环从0开始，到c（背包容量）结束

Ⅳ.C语言中用到的数学函数是fmax()

//01背包问题 

#include
#include
//using namespace std;

const int N=1e6+10;
int v[N];
int w[N];
int dp[N][N];

int main()
{
    int n,c;
    scanf("%d %d",&n,&c);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d %d",&w[i],&v[i]);
    }

    for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=c;j++)
		{
			if(j

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/676416.html