Bessie has gone to the mall‘s jewelry store and spies a charm bracelet. Of course, she‘d like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charm iin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a ‘desirability‘ factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
4 6 1 4 2 6 3 12 2 7
23
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int dp[30000]; 5 int w[30000]; 6 int v[30000]; 7 8 int main(){ 9 int n,m; 10 cin>>n>>m; 11 memset(dp,0,sizeof(dp)); 12 for(int i=1;i<=n;i++){ 13 cin>>w[i]>>v[i]; 14 } 15 for(int i=1;i<=n;i++){ 16 for(int j=m;j>=w[i];j--){ 17 dp[j]=max(dp[j],dp[j-w[i]]+v[i]); 18 } 19 } 20 cout<<dp[m]<<endl; 21 return 0; 22 }
转自https://www.cnblogs.com/caiyishuai/p/8945331.html
N 个物品每个物品有价值v[i]，重量w[i]， 给定背包最大承重M，求背包能够装载的最大价值。每个物品只有放入背包和不放入背包两种选择。
这是典型的0-1背包问题。
代码的时间上限是O(nm), 对于每个物品i, 它所要遍历的整数区间都是[ci, m]
原文：https://www.cnblogs.com/aiqinger/p/12595395.html