考研算法47天：01背包

问题描述 

算法详细步骤

代码随想录 (programmercarl.com)

ac代码

#include <iostream>
using namespace std;
int bag[1001];
int bagMax[1001];
int bagvalue[1001];
int main(){
     int n,v;
     cin>>n>>v;
     for(int i=0;i<n;i++){
         cin>>bag[i]>>bagvalue[i];
     }
     for(int j=0;j<n;j++){
         //为啥要将物品遍历放到外面因为如果放到里面的话就会重复放入背包
         //但是本题的每一个物品只有一个
         //并且如果遍历背包是顺序的方式的话也会重复，举个例子
         //物体一的价值为100 但是重量只有1当遍历重量为2的时候我们第一次背包大小为1的时候已经放入了。
         //但是此时还是会继续放入物品一，大小够。
         //所以反过来就不会。从最大的开始遍历的话，物品在背包最大时不会重复放入
         //具体的看下图
         for(int i=v;i>=1;i--){
         if(bag[j]<=i){
         bagMax[i] = max(bagMax[i],bagMax[i-bag[j]]+bagvalue[j]);
         }
         }
     }
     cout<<bagMax[v];
    return 0;
}