Златопольский 8.47. Вложенные циклы

[Dezikk]

Имееться 10 гирь весом 100 200 300 500 1000 1200 1400 1500 2000 3000 грамм каждая. Сколькими способами гирями этого набора можно составить вес в v грамм.
Вот собственно к чему пришел, но не правильно. Помогите!

int v,vv,count=0;		//zlatopol 8.47
int g[10]={100,200,300,500,1000,1200,1400,1500,2000,3000};
cin>>v;
vv=v;
for (int j=9;j>=0;j--)
{
vv=v;
if (g[j]>vv) continue;
vv-=g[j];
if (vv==0) {count++;vv+=g[j];}
for (int i=j-1;i>=0;i--)
{
	if (g[i]>vv) continue;
	vv-=g[i];
	if (vv==0) {count++;vv+=g[i];}
}
}

cout<<count<<endl;

return 0;
}

[Blind Guard]

Т.е., например, вес в 500 грамм можно собрать 5-ю способами?

100*5 = 500
100*3+200 = 500
100+200*2 = 500
100*2+300 = 500
200+300 = 500

Я правильно понял задание?

[Dezikk]

Сообщение от Blind Guard

Т.е., например, вес в 500 грамм можно собрать 5-ю способами?

100*5 = 500
100*3+200 = 500
100+200*2 = 500
100*2+300 = 500
200+300 = 500

Я правильно понял задание?

Нет. В нашем распоряжении только по ОДНОЙ гире указанных весов. Те
1500=1500
1500=1400+100
1500=1200+300
1500=1200+200+100
1500=1000+500
1500=1000+300+200

[Dezikk]

Все, больше не знаю куда дальше. Некоторые правильно считает, некоторые нет. Скоро лопнет голова. Может я вообще не в те дебри полез?!

PHP код:

int v,vv,count=0;        //zlatopol 8.47
int g[10]={100,200,300,500,1000,1200,1400,1500,2000,3000};
cin>>v;
vv=v;
for (int j=9;j>=0;j--)
{
    vv=v;
    if (g[j]>vv) continue;
for (int i=j;i>=0;i--)
{
    if (g[i]>vv) continue;
for (int k=j;k>=0;k--)
{
    if (g[k]>vv) continue;
    vv-=g[k];
    if (vv==0) {count++; break;}
}
    if (vv==0) continue;
}
    if (vv==0) continue;
}

cout<<count<<endl; 


[Dezikk]

Закройте пожалуйста тему, решение найдено.

[sVasilich]

А можно его выложить, раз найдено? Интересно

Сам долго думал над задачей. Придумал так, вроде даже работает, хотя, подозреваю что bitset нельзя было использовать:

int main()
{

	int desiredWeights;        //zlatopol 8.47 
	int poises[10]={100,200,300,500,1000,1200,1400,1500,2000,3000}; 
	cin>>desiredWeights; 
	
	int maxIndex = 0;
	for(int z=0; z<10; z++){
		if(poises[z]>desiredWeights)
			break;
		maxIndex=z;
	}


	
	int combinations = 0;
	int maxComb = pow((double)2,maxIndex+1);

	for(int curComb=0; curComb<maxComb; curComb++){
		bitset<10> mask(curComb);
		int tmpSum = 0;
		for(int i=0; i<=maxIndex; i++)
			if(mask.test(i))
				tmpSum+=poises[i];

		if(tmpSum==desiredWeights)
			++combinations;
	}

	cout<<combinations;
	cin.get();
}

[Dezikk]

Если кому то интересно , я пришел к такому решению. Но оно как всегда оказалось неправильным... Опять ...

PHP код:

Int v,vv,count=0;
int g[10]={100,200,300,500,1000,1200,1400,1500,2000,3000};
cin>>v;
vv=v;
for (int j=9;j>=0;j--)
{
    vv=v;
    if (g[j]>vv) continue;
    vv-=g[j];
    if (vv==0) {count++; continue;}
for (int i=j-1;i>=0;i--)
{
    if (g[i]>vv) continue;
    vv-=g[i];
    if (vv==0) {count++; if (g[i]>200) vv=g[i];}
for (int k=i-1;k>=0;k--)
{
    if (g[k]>vv) continue;
    vv-=g[k];
    if (vv==0) {count++; if (g[i]>200) vv=g[k];}
}
}
}

cout<<count<<endl; 


А вот это ПРАВИЛЬНОЕ решение мне подсказали на соседнем форуме.

PHP код:

int g[10]={100,200,300,500,1000,1200,1400,1500,2000,3000};  
  int mask, sum, bit, count=0;
  int v;
  cin>>v; 
  for (int i=1; i<=0x3FF;i++){
    mask=1, sum=bit=0;
    while(mask<=i){
      if(i&mask) sum+=g[bit];
      bit++;
      mask<<=1;
    }
    if (sum==v) count++;
  }
  cout<<count<<endl; 


Но есть одно большое но! В выложенном правильном варианте используються функции, которые мы еще не рассматривали на занятиях, поэтому по идее препод:
1-либо лоханулся и дал слишком продвинутое задание
2- либо существует более простой вариант.
Собственно задача в учебнике Златопольского находиться в разделе "Вложенные циклы. Работа с целыми числами"... Вот такие пироги...

[Dezikk]

Сообщение от sVasilich

Сам долго думал над задачей. Придумал так, вроде даже работает, хотя, подозреваю что bitset нельзя было использовать:

Большое спасибо, но пока не имею возможности потестить предложенный вариант решения. Потом отпишусь

И кстати, какие заголовочные файлы подключать кроме math.h?

[sVasilich]

Вот:

#include <iostream>
#include <bitset>
#include <math.h>

Ну да, решение на соседнем форуме по такому же принципу, как моё, просто мне лень было вспоминать как со сдвигами работать и я доверил перевод из десятичной в двоичную контейнеру bitset.

По-моему, эта задача через вложенные циклы не решается. Либо маской, либо рекурсивными функциями. Хотя рекурсию я составить для этого случая тоже затрудняюсь.