#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,Alv,Ans=1e9,Tot,Opt[100005];
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d",&n,&Alv);Tot=Alv*2;
    memset(Opt,63,sizeof(Opt));Opt[0]=0;
    for(int i=1;i<=n;i++){
        int V,p;scanf("%d%d",&V,&p);
        for(int j=V;j<=Tot;j++)
        Opt[j]=min(Opt[j-V]+p,Opt[j]);
    }
    for(int i=Alv;i<=Tot;i++) Ans=min(Opt[i],Ans);
    printf("%d\n",Ans);
    return 0;
}

[USACO08NOV] Buying Hay S

题意

知道各个货品和最大价值最小的大小，反求背包最小容量。

题解

用二分法求背包最小容量，具体见代码：

#include<bits/stdc++.h>
using namespace std;
int m,n;//m最大价值最小的大小，n货品数量
int w[105],C[105];//w存货品大小，C存货品价值
int dp[50005];
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>C[i]>>w[i];
	}
	int l=0,r=100000;
	while(l<r){//二分
		int mid=(l+r)/2;//假设背包容量为mid
	    for(int i=1;i<=n;i++){
		    for(int c=1;c<=mid;c++){
			    if(w[i-1]<=c)
			    dp[c]=max(dp[c],dp[c-w[i-1]]+C[i-1]);
		    }
	    }//dp算出最大价值
	    if(dp[mid]<m)//如果最大价值小于m
	    l=mid+1;//更新区间
	    else
	    r=mid;//更新区间
	}
	cout<<l;//输出背包容量
	return 0;
}

点赞！！！