这道题的状态转移方程还是挺容易找的,操作稍微费点心就可以了。
参考代码:
#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); using namespace std; const int maxn=31; const int value_max=20005; int arry[maxn]= {0}; //物品数量 int dp[value_max]= {0}; //dp int v,n; //v为箱子容量,n为物品数量 void dp_calc() { for(int i=1; i<=n; i++) for(int j=v; j>=arry[i]; j--) dp[j]=max(dp[j],dp[j-arry[i]]+arry[i]); } int main() { hh; cin>>v; cin>>n; for(int i=1; i<=n; i++) cin>>arry[i]; dp_calc(); cout<<v-dp[v]<<endl; return 0; }
才发现排版有点问题,修改一下
#include<bits/stdc++.h> #define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); using namespace std; const int maxn=20005; int v,n; int w[maxn]={0}; int dp[maxn]={0}; int main(){ hh; cin>>v; cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; } for(int i=1;i<=n;i++){ for(int j=v;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+w[i]); } } cout<<v-dp[v]<<endl; return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题9.2 (C语言代码)浏览:687 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:2468 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:742 |
打水问题 (C语言代码)浏览:1066 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:1233 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:869 |
母牛的故事 (C语言代码)浏览:940 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:575 |
C二级辅导-温度转换 (C语言代码)浏览:718 |
DNA (C语言代码)浏览:735 |