以前，有个神秘的院子里面有三种苹果，每个苹果的数量是无限的。有一个小姑娘带了一个大袋子来到院子，她从来没见过这么多的苹果。每种苹果都有大小以及出售的价格，小姑娘想获得最大的利润，但是她不知道怎么才能做到。于是她来向你寻求帮助，你能告诉她能获得的最大价值吗？
第一行一个整数T(T <= 50)，表示测试数据的组数。
每组测试数据有四行组成，前三行每行有两个整数S和P，分别表示每种苹果的大小(1 <= S <= 100)和价格(1 <= P <= 10000)
第四行有一个整数V(1 <= V <= 100,000,000)表示小姑娘袋子的大小。
每组测试数据输出组数和小姑娘能得到的最大的价值。
1 1 1 2 1 3 1 6
Case 1: 6
背包容量100000000太大了，一维数组开不了。
就先去一大部分容量来装性价比最高的苹果，即(价格/重量)最大的苹果。
剩下一小部分的背包容量使用完全背包。
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int inf = 0x3f3f3f3f; typedef long long ll; struct Node { ll s,p; double v; }node[4]; bool cmp(Node p,Node q) { return p.v < q.v; } ll dp[1101]; int main() { int t,v,k = 0; cin >> t; while(t--) { k++; for(int i = 0; i < 3; i++) { cin >> node[i].s >> node[i].p; node[i].v = node[i].s*1.0/node[i].p; } cin >> v; sort(node,node + 3,cmp); ll ans = 0; if(v > 1000) { ans = ((v-1000)/node[0].s)*node[0].p; v = 1000 + (v-1000)%node[0].s; } memset(dp,0,sizeof(dp)); for(int i = 0; i < 3; i++) { for(ll j = node[i].s; j <= v; j++) { dp[j] = max(dp[j],dp[j-node[i].s] + node[i].p); } } ans += dp[v]; cout <<"Case " << k << ": " << ans << endl; } return 0; }
原文：https://www.cnblogs.com/LLLAIH/p/11764258.html