动态规划问题-01背包

    科技2022-07-17  122

    动态规划问题01背包

    题目描述 一个旅行者有一个最多能用m公斤的背包,现在有n件物品,它们的重量分别是W1,W2,…,Wn,它们的价值分别为C1,C2,…,Cn.若每种物品只有一件求旅行者能获得最大总价值。 输入 第1行:两个整数,M(背包容量,M<=200)和N(物品数量,N<=30);

    第2…N+1行:每行二个整数Wi,Ci,表示每个物品的重量和价值。

    输出 仅一行,一个数,表示最大总价值。 样例输入 Copy 10 4 2 1 3 3 4 5 7 9 样例输出 Copy 12

    思路:动态规划,运用二维数组解决

    视频教程地址 这是一个由底到上的过程,将可能的情况按二维数组DP[]进行储存,最后输出即可;

    公式

    当j>W[i]的时候:DP[i][j]=DP[i-1][j];

    当j>W[i]的时候: DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i])+C[i];

    一定要判断,不然下标会取到负值,,,;

    //W[i]是第i个的重量,C[i]是第i个物品的价值;

    #include<iostream>// 当j>W[i]的时候:DP[i][j]=DP[i-1][j]; #include<bits/stdc++.h>// 当j>W[i]的时候: DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i])+C[i]; using namespace std; int max(int a, int b) { if (a >= b) return a; else return b; } int main(){ int M,N; cin >> M >> N; int W[35],C[35];//W[i]是重量,C[i]是价值 for(int i=1;i<=N;i++){ cin >> W[i] >> C[i]; } int DP[35][250];//用于储存 memset(DP,0,sizeof(DP));//置0 for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ if(j>=W[i]) DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+C[i]); else DP[i][j]=DP[i-1][j]; } } cout << DP[N][M] << endl; return 0; }
    Processed: 0.010, SQL: 8