前车之鉴

起因

现在从n个物品中，任取若干个装入箱内（也可以不取）

我短路的脑子：n个物品，每个物品任取若干，也可不取

经过

01背包—》完全背包

#include<bits/stdc++.h>
using namespace std;

int v,n,wei[50],val[50];
int dp[20010];

int main(){
	cin>>v>>n;
	for(int i=1;i<=n;i++){
		cin>>wei[i];
		val[i]=wei[i];
	} 
	for(int i=1;i<=n;i++){
		for(int j=wei[i];j<=v;j++){//这个循环错了
			dp[j]=max(dp[j],dp[j-wei[i]]+val[i]);
		}
	}
	cout<<v-dp[v]<<endl;
	return 0;
}

结果

反思

十年OI一场空，大脑一定不放松