Sample Input
735 3 4 125 6 5 3 350633 4 500 30 6 100 1 5 0 1735 00 3 10 100 10 50 10 10
Sample Output
73563000
题意：你的银行卡里有 cash 元，而ATM机里有 n 种面值的钱，n行每种钱的数量和面值。
问 最多能从这台ATM机里取出多少钱。
裸的完全背包
可是我居然写错了。。。。
在当前物品的数量*价值 大于等于 背包容量时，就可以将当前物品的数量视作无限，for循环的时候就从小到大正序遍历。
小于等于的时候 就将物品数量转换成二进制下的01背包 这里是01背包！！！
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int cash, n;int c[15],w[15];int dp[100005];void CompletePack(int c,int w){if(c*w>=cash){ // 完全背包for(int j=w;j<=cash;j++)dp[j] = max(dp[j],dp[j-w]+w);}else { // 多次01背包int k = 1;while(k<c){for(int j=cash;j>=w*k;j--)dp[j] = max(dp[j],dp[j-w*k]+w*k);c -= k;k <<= 1;}for(int j=cash;j>=w*c;j--)dp[j] = max(dp[j],dp[j-w*c]+w*c);}}int main(){while(scanf("%d%d",&cash,&n)!=EOF){memset(dp,0,sizeof(dp));for(int i=0;i<n;i++){scanf("%d%d",&c[i],&w[i]);}for(int i=0;i<n;i++){CompletePack(c[i],w[i]);}printf("%d\n",dp[cash]);}return 0;}
View Code
