题目:
有重量分别为3,5,7公斤的三种货物,和一个载重量为X公斤的箱子
(不考虑体积等其它因素,只计算重量)
需要向箱子内装满X公斤的货物,要求使用的货物个数尽可能少(三种货物数量无限)
解析:
对7取余,对余数进行讨论即可
余数为1,3,5,则可以装满,1可以视为1+7=3+5,是之前的count+1
余数为2,4,6,也可以装满,2可以视为2+7=3+3+3,4可以视为4+7=5+3+3,6=3+3是之前的count+2
代码:
- 普通法:
int main() { int x; cin>>x; int count = 0; if(x==1 || x==2 || x==4) cout<<-1; else{ count = x/7; int n = x%7; if(n==1 || n==3|| n==5){ count +=1; } else if(n==2||n==4||n==6){ count +=2; } cout<<count; } return 0; }
- 动态规划
#include<iostream> #include<vector> #define MAX 10000 using namespace std; int min(int a,int b){ return a<b?a:b; } int main(){ int X; cin>>X; vector<int> dp(X+1,MAX); dp[3]=1; dp[5]=1; dp[6]=2; dp[7]=1; for(int sum=8;sum<=X;sum++){ //装8 可以看作5装3 3装5 1装7 这三个策略演变过来取最小的+1 dp[sum]=min(dp[sum-3],min(dp[sum-5],dp[sum-7]))+1; } cout<<(dp[X]>=MAX?-1:dp[X])<<endl; return 0; }