P2871 [USACO07DEC]手链Charm Bracelet
题解:01背包
#include<iostream> #include<cstdio> #include<cstring> #define maxn 5000 using namespace std; int n,m,c[maxn],w[maxn],f[maxn*3]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d%d",&c[i],&w[i]); for(int i=1;i<=n;i++) for(int j=m;j>=c[i];j--) f[j]=max(f[j],f[j-c[i]]+w[i]); printf("%d ",f[m]); return 0; }
P2639 [USACO09OCT]Bessie的体重问题Bessie's We…
题目大意:最多吃H公斤,每捆草a公斤,最多吃多少公斤。
题解:01背包
代码:
#include<iostream> #include<cstdio> using namespace std; int n,m,w[50000],f[50000]; int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) f[j]=max(f[j],f[j-w[i]]+w[i]); printf("%d ",f[m]); return 0; }
P2347 砝码称重
题目大意:设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=1000)
题解:搜索 / 背包
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int ans; int a[10],w[1020]; int v[7]={0,1,2,3,5,10,20}; void dfs(int now,int vv){ w[vv]=true; for(int i=now;i<=6;i++){ if(a[i]){ a[i]--; dfs(i,vv+v[i]); a[i]++; } } } int main(){ for(int i=1;i<=6;i++)scanf("%d",&a[i]); dfs(1,0); for(int i=1;i<=1000;i++)if(w[i])ans++; printf("Total=%d ",ans); return 0; }